Submission #138840

#	Time	Username	Problem	Language	Result	Execution time	Memory
138840		MrBrionix	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	793 ms	95376 KiB

scrivener

#include<bits/stdc++.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
using namespace std;

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

int siz[1000005],succ[1000005][22],cont;
char c[1000005];

void Init(){
    
    siz[0]=0;
    for(int i=0;i<1000005;i++)for(int j=0;j<22;j++)succ[i][j]=-1;
    cont=1;
    succ[0][0]=0;
    return;
}


void TypeLetter(char L){
    
    c[cont]=L;
    siz[cont]=siz[cont-1]+1;
    
    succ[cont][0]=cont;
    succ[cont][1]=succ[cont-1][0];
    
    for(int i=2;i<22;i++){
        if(succ[cont][i-1]!=-1)
        succ[cont][i]=succ[succ[cont][i-1]][i-1];
        else break;
    }
    
    cont++;
}


void UndoCommands(int U){
    
    siz[cont]=siz[cont-1-U];
    for(int i=0;i<22;i++){
        if(succ[cont-1-U][i]!=-1)
        succ[cont][i]=succ[cont-1-U][i];
        else break;
    }
    
    cont++;
}

char GetLetter(int P){
    
    int num=siz[cont-1]-1-P,pos=cont-1;

    for(int j=21;j>=1;j--){
        if((1ll<<(j-1ll))<=num){
            num-=(1ll<<(j-1ll));
            pos=succ[pos][j];
        }
        if(num==0)break;
    }
    
    /*
    cout<<"debug"<<endl;
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            cout<<succ[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"-------------"<<endl;
    */
    
    return c[succ[pos][0]];
}

/*

int main() {
  Init();

  int cmd_num,tmp;
  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;

}*/

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