oj.uz

Submission #63659

# Submission time Handle Problem Language Result Execution time Memory
63659 2018-08-02T11:23:20 Z evpipis Crayfish scrivener (IOI12_scrivener) C++11
0 / 100
 351 ms 93144 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-1] = 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 78584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 78700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 78784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 318 ms 91836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 351 ms 93144 KB Output isn't correct
2 Halted 0 ms 0 KB -