Submission #63660

#	Time	Username	Problem	Language	Result	Execution time	Memory
63660		evpipis	Crayfish scrivener (IOI12_scrivener)	C++11	34 / 100	1086 ms	111316 KiB

scrivener

#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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40