Submission #370520

#	Time	Username	Problem	Language	Result	Execution time	Memory
370520		ijxjdjd	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	909 ms	164204 KiB

scrivener

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

using namespace std;

using ll = long long;

const int MAXN = (int)(1e7) + 5;
const int MAXK = 20;

int up[MAXN][MAXK];
int undo[MAXN][MAXK];
int depth[MAXN];
char res[MAXN];
int cnt = 1;
int liftUp(int u, int d) {
    for (int i = 0; i < MAXK; i++) {
        if (d&(1<<i)) {
            u = up[u][i];
        }
    }
    return u;
}
int liftUndo(int u, int d) {
    for (int i = 0; i < MAXK; i++) {
        if (d&(1<<i)) {
            u = undo[u][i];
        }
    }
    return u;
}
void Init() {

}

void TypeLetter(char L) {
    res[cnt] = L;
    up[cnt][0] = cnt-1;
    undo[cnt][0] = cnt-1;
    for (int i = 1; i < MAXK; i++) {
        up[cnt][i] = up[up[cnt][i-1]][i-1];
//        undo[cnt][i] = undo[undo[cnt][i-1]][i-1];
    }
    depth[cnt] = depth[cnt-1]+1;
    cnt++;
}

void UndoCommands(int U) {
    int next = cnt-1-U;
    res[cnt] = res[next];
    up[cnt][0] = up[next][0];
    undo[cnt][0] = cnt-1;
    for (int i = 1; i < MAXK; i++) {
        up[cnt][i] = up[up[cnt][i-1]][i-1];
//        undo[cnt][i] = undo[undo[cnt][i-1]][i-1];
    }
    depth[cnt] = depth[next];
    cnt++;
}
char GetLetter(int P) {
    return  res[liftUp(cnt-1, depth[cnt-1] - P - 1)];
}
//int main() {
//  Init();
//
//  int cmd_num, tmp;
//  tmp = scanf("%d", &cmd_num);
//
//  int i;
//  for (i = 0; i < cmd_num; i++) {
//    char cmd;
//    int tmp = scanf(" %c", &cmd);
//    if (cmd == 'T') {
//      char letter;
//      tmp = scanf(" %c", &letter);
//      TypeLetter(letter);
//    }
//    else if (cmd == 'U') {
//      int number;
//      tmp = scanf("%d", &number);
//      UndoCommands(number);
//    }
//    else if (cmd == 'P') {
//      int index;
//      char letter;
//      tmp = scanf("%d", &index);
//      letter = GetLetter(index);
//      printf("%c\n", letter);
//    }
//  }
//
//  puts("Let's test for cheating!!");
//
//  return 0;
//
//}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40