Submission #918357


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <array>
#include <list>
#include <stack>
#include <valarray>

using namespace std;

typedef unsigned uint;
typedef long long Int;
typedef unsigned long long UInt;

const int INF = 1001001001;
const Int INFLL = 1001001001001001001LL;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<typename T> void chmin(T& a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T& a, T b) { if (a < b) a = b; }
int in() { int x; scanf("%d", &x); return x; }
double fin() { double x; scanf("%lf", &x); return x; }
Int lin() { Int x; scanf("%lld", &x); return x; }

char S[500000];
int M[100050][26][26], PF[100050];

struct trie {
  int nxt[26], num, id;
  trie() { fill(nxt, nxt + 26, -1); num = 0; id = -1; }
} T[500000];
int tnum = 1, troot = 0;
int alloc() {
  return tnum++;
}

void trie_add(char* s, int id) {
  int p = troot;
  for (int i = 0; s[i]; ++i) {
    int c = s[i] - 'a';
    ++T[p].num;
    if (T[p].nxt[c] == -1) {
      T[p].nxt[c] = alloc();
    }
    p = T[p].nxt[c];
  }
  ++T[p].num;
  T[p].id = id;
}

int CM[26][26];

void trie_precalc(int p, int pf) {
  if (T[p].id >= 0) {
    PF[T[p].id] = pf;
    memcpy(M[T[p].id], CM, sizeof(CM));
    ++pf;
  }
  for (int i = 0; i < 26; ++i) {
    if (T[p].nxt[i] >= 0) {
      for (int j = 0; j < 26; ++j) {
        if (i != j && T[p].nxt[j] >= 0) {
          CM[i][j] += T[T[p].nxt[j]].num;
        }
      }
      trie_precalc(T[p].nxt[i], pf);
      for (int j = 0; j < 26; ++j) {
        if (i != j && T[p].nxt[j] >= 0) {
          CM[i][j] -= T[T[p].nxt[j]].num;
        }
      }
    }
  }
}

int main() {
  int N = in();
  for (int i = 0; i < N; ++i) {
    scanf("%s", S);
    trie_add(S, i);
  }

  trie_precalc(troot, 0);

  int Q = in();
  char A[32];
  int O[32];
  for (int i = 0; i < Q; ++i) {
    int k = in() - 1;
    scanf("%s", A);
    for (int j = 0; j < 26; ++j) {
      O[A[j] - 'a'] = j;
    }
    int res = 1 + PF[k];
    for (int a = 0; a < 26; ++a) {
      for (int b = 0; b < 26; ++b) {
        if (a != b && O[a] > O[b]) {
          res += M[k][a][b];
        }
      }
    }
    printf("%d\n", res);
  }

  return 0;
}

Submission Info

Submission Time
Task E - Lexicographical disorder
User japlj
Language C++14 (GCC 5.4.1)
Score 1100
Code Size 2587 Byte
Status AC
Exec Time 689 ms
Memory 320000 KB

Compile Error

./Main.cpp: In function ‘int in()’:
./Main.cpp:34:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int in() { int x; scanf("%d", &x); return x; }
                                  ^
./Main.cpp: In function ‘double fin()’:
./Main.cpp:35:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 double fin() { double x; scanf("%lf", &x); return x; }
                                          ^
./Main.cpp: In function ‘Int lin()’:
./Main.cpp:36:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 Int lin() { Int x; scanf("%lld", &x); return x; }
                                     ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:92:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", S);...

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1100 / 1100
Status
AC × 2
AC × 42
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt AC 689 ms 320000 KB
02.txt AC 689 ms 320000 KB
03.txt AC 688 ms 320000 KB
04.txt AC 689 ms 320000 KB
05.txt AC 539 ms 161280 KB
06.txt AC 431 ms 65920 KB
07.txt AC 420 ms 57984 KB
08.txt AC 418 ms 55936 KB
09.txt AC 415 ms 55808 KB
10.txt AC 419 ms 59904 KB
11.txt AC 454 ms 135040 KB
12.txt AC 500 ms 171008 KB
13.txt AC 552 ms 211840 KB
14.txt AC 421 ms 65920 KB
15.txt AC 410 ms 55680 KB
16.txt AC 415 ms 59904 KB
17.txt AC 435 ms 74240 KB
18.txt AC 354 ms 57728 KB
19.txt AC 354 ms 57728 KB
20.txt AC 355 ms 57728 KB
21.txt AC 354 ms 57728 KB
22.txt AC 353 ms 57728 KB
23.txt AC 488 ms 158336 KB
24.txt AC 454 ms 133760 KB
25.txt AC 498 ms 169728 KB
26.txt AC 354 ms 57728 KB
27.txt AC 371 ms 65792 KB
28.txt AC 378 ms 69888 KB
29.txt AC 362 ms 56832 KB
30.txt AC 432 ms 103040 KB
31.txt AC 376 ms 58624 KB
32.txt AC 365 ms 55808 KB
33.txt AC 375 ms 57600 KB
34.txt AC 371 ms 56704 KB
35.txt AC 378 ms 56064 KB
36.txt AC 685 ms 320000 KB
37.txt AC 392 ms 64640 KB
38.txt AC 392 ms 64640 KB
39.txt AC 66 ms 54912 KB
40.txt AC 66 ms 54912 KB
s1.txt AC 66 ms 54912 KB
s2.txt AC 65 ms 54912 KB