oj.uz

Submission #63660

# Submission time Handle Problem Language Result Execution time Memory
63660 2018-08-02T11:26:35 Z evpipis Crayfish scrivener (IOI12_scrivener) C++11
34 / 100
 1000 ms 111316 KB 
#include <bits/stdc++.h>
using namespace std;

//#define TEST

const int len = 1e6+5, lg = 20;
int dp[len][lg], par[len], dep[len], nod[len], pos;
char val[len];

void Init(){
    pos = 0;
    for (int i = 0; i < len; i++)
        for (int j = 0; j < lg; j++)
            dp[i][j] = -1;
}

void TypeLetter(char L){
    pos++;
    nod[pos] = pos;
    par[pos] = nod[pos-1];
    val[pos] = L;
    dep[pos] = dep[par[pos]]+1;

    dp[pos][0] = par[pos];
    for (int j = 1; j < lg; j++)
        if (dp[pos][j-1] != -1)
            dp[pos][j] = dp[dp[pos][j-1]][j-1];
}

void UndoCommands(int U){
    pos++;
    nod[pos] = nod[pos-U-1];
}

char GetLetter(int P){
    int cur = nod[pos];
    for (int j = lg-1; j >= 0; j--)
        if (dp[cur][j] != -1 && dep[dp[cur][j]] > P)
            cur = dp[cur][j];

    return val[cur];
}

#ifdef TEST
int main() {
  freopen("example.txt", "r", stdin);
  Init();

  int cmd_num;
  int tmp = scanf("%d", &cmd_num);
  assert(tmp == 1);

  int i;
  for (i = 0; i < cmd_num; i++) {
    char cmd;
    tmp = scanf(" %c", &cmd);
    assert(tmp == 1);
    if (cmd == 'T') {
      char letter;
      tmp = scanf(" %c", &letter);
      assert(tmp == 1);
      TypeLetter(letter);
    }
    else if (cmd == 'U') {
      int number;
      tmp = scanf("%d", &number);
      assert(tmp == 1);
      UndoCommands(number);
    }
    else if (cmd == 'P') {
      int index;
      char letter;
      tmp = scanf("%d", &index);
      assert(tmp == 1);
      letter = GetLetter(index);
      printf("%c\n", letter);
    }
  }

  puts("Let's test for cheating!!");

  return 0;

}
#endif // TEST

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 78584 KB Output is correct
2 Correct 74 ms 78692 KB Output is correct
3 Correct 76 ms 78732 KB Output is correct
4 Correct 94 ms 78760 KB Output is correct
5 Correct 82 ms 78816 KB Output is correct
6 Correct 81 ms 78824 KB Output is correct
7 Correct 89 ms 78824 KB Output is correct
8 Correct 82 ms 78824 KB Output is correct
9 Correct 91 ms 78908 KB Output is correct
10 Correct 83 ms 78908 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 78908 KB Output is correct
2 Correct 83 ms 78908 KB Output is correct
3 Correct 93 ms 78968 KB Output is correct
4 Correct 86 ms 78968 KB Output is correct
5 Correct 84 ms 79024 KB Output is correct
6 Correct 75 ms 79024 KB Output is correct
7 Correct 84 ms 79024 KB Output is correct
8 Correct 70 ms 79024 KB Output is correct
9 Correct 80 ms 79024 KB Output is correct
10 Correct 89 ms 79024 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 79024 KB Output is correct
2 Correct 88 ms 79044 KB Output is correct
3 Correct 92 ms 79060 KB Output is correct
4 Correct 89 ms 79168 KB Output is correct
5 Correct 88 ms 79168 KB Output is correct
6 Correct 91 ms 79168 KB Output is correct
7 Correct 98 ms 79168 KB Output is correct
8 Correct 90 ms 79292 KB Output is correct
9 Correct 89 ms 79292 KB Output is correct
10 Correct 86 ms 79292 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 933 ms 88800 KB Output is correct
2 Correct 853 ms 91908 KB Output is correct
3 Correct 453 ms 91908 KB Output is correct
4 Correct 468 ms 92340 KB Output is correct
5 Correct 690 ms 92340 KB Output is correct
6 Correct 528 ms 96832 KB Output is correct
7 Correct 878 ms 101212 KB Output is correct
8 Correct 846 ms 107520 KB Output is correct
9 Execution timed out 1068 ms 111316 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 111316 KB Time limit exceeded
2 Halted 0 ms 0 KB -