제출 #79064

#제출 시각아이디문제언어결과실행 시간메모리
79064TAMREF크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++11
34 / 100
1079 ms80736 KiB
#include <bits/stdc++.h> using namespace std; const int mx = 1e6 + 5; const int lg = 20; /* struct node{ node(){} node(int c, char x, int i) : c(c),x(x),i(i) { memset(p,-1,sizeof(p)); } int p[lg], c; char x; int i; void show(){ printf("x = %c, i = %d, c = %d\n",x,i,c); } }; */ int C[mx], I[mx]; char X[mx]; int p[lg][mx]; //vector<node> N; int n; void show(int i){ printf("C : %d I : %d X : %c\n",C[i],I[i],X[C[i]]); } void Init() { //memset(p,-1,sizeof(p)); } void TypeLetter(char L) { ++n; //printf("Type(%c)\n",L); //printf(""); //N.emplace_back(); //puts("f1"); //N[n] = node(0, L, !n ? 0 : N[n-1].i + 1); I[n] = I[n-1] + 1; C[n] = n; X[n] = L; p[0][n] = n - 1; for(int j = 1; j < lg; j++){ if(!p[j-1][n]) break; else{ p[j][n] = p[j-1][p[j-1][n]]; } } //puts("f2"); //node &x = N[n]; //puts("f3"); //x.p[0] = (!n ? -1 : n-1); //puts("f4"); /* for(int j = 1; j < lg; j++){ //printf("j = %d\n",j); if(x.p[j-1] != -1) x.p[j] = N[x.p[j-1]].p[j-1]; else break; } */ //puts("f5"); //x.c = n; //N[n].show(); //show(n); } void UndoCommands(int U) { ++n; //printf("Undo(%d)\n",U); //N.emplace_back(); if(U == n){ I[n] = 0; C[n] = 0; X[n] = 'U'; //N[n] = node(-1, 'U', -1); //node &x = N[n]; //++n; return; } /* node p = N[n - 1 - U]; N[n] = node(p.c, 'U', p.i); node &x = N[n]; x.p[0] = n - 1 - U; for(int j = 1; j < lg; j++){ if(x.p[j-1] != -1) x.p[j] = N[x.p[j-1]].p[j-1]; else break; } */ I[n] = I[n - 1 - U]; C[n] = C[n - 1 - U]; p[0][n] = n - 1 - U; for(int j = 1; j < lg; j++){ if(!p[j-1][n]) break; else{ p[j][n] = p[j-1][p[j-1][n]]; } } //show(n); //N[n].show(); //++n; } char GetLetter(int P) { //printf("Get(%d)\n",P); //node b = N[n-1]; ++P; int b = n; for(int j = lg-1; j >= 0; j--){ //printf("b = %d\n",b); if(I[b] == P) return X[C[b]]; if(p[j][b] && I[p[j][b]] >= P) b = p[j][b]; } /* for(int j = lg; j >= 0; j--){ if(b.i == P) return N[b.c].x; if(b.p[j] != -1 && N[b.p[j]].i >= P) b = N[b.p[j]]; } */ //printf("bi : %d\n",b->i); //puts("asdf"); //return b.i == P ? N[b.c].x : N[N[b.p[0]].c].x; return I[b] == P ? X[C[b]] : X[C[p[0][b]]]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...