Submission #589953

#	Time	Username	Problem	Language	Result	Execution time	Memory
589953		daria	Crayfish scrivener (IOI12_scrivener)	C++14	0 / 100	111 ms	262144 KiB

scrivener

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define N (ll)1e6

ll n = 0, t = 0;
ll dpt[N], par[N][20];
ll len[N], pos[N];
string s[N][20];
char c[N];


string psum(ll a){
 string r;
 ll p = dpt[a];
 for(ll i=0; i<20; ++i)
  if(p & (1 << i)){
   r = s[a][i] + r;
   a = par[a][i];
  }
 return r;
}


ll anc(ll a, ll p){
 for(ll i=0; i<20; ++i)
  if(p & (1 <<i))
   a = par[a][i];
 return a;
}


void Init(){

}

void TypeLetter(char L) {
 ll curr = pos[t];
 n++;
 t++;
 pos[t] = n;

 //aggiungo un nuovo nodo
 c[n] = L;
 dpt[n] = dpt[curr] + 1;

 par[n][0] = curr;
 for(ll i=1; i<20; ++i)
  par[n][i] = par[par[n][i-1]][i-1];

 s[n][0] = L;
 for(ll i=1; i<20; ++i)
  s[n][i] = s[par[n][i-1]][i-1] + s[n][i-1];

 //cout << psum(pos[t]) << endl;

}

void UndoCommands(int U) {
 t++;
 pos[t] = pos[t-U-1];
 //cout << psum(pos[t]) << endl;
}

char GetLetter(int P){
 ll curr = pos[t];
  //cout << psum(pos[t]) << endl << "get: ";;
 return c[anc(curr, dpt[curr]-P-1)];
}

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