제출 #1269181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269181		nerrrmin	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++20	100 / 100	415 ms	71264 KiB

scrivener

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e6 + 10;
char last;
int n;
char onv[maxn];
int from[maxn], jump[maxn][22], len[maxn];
vector < int > g;
int curr;
void Init()
{
    n = 1;
    onv[1] = '-';
    len[1] = 0;
    curr = 1;
    g.pb(1);
}

void TypeLetter(char L) {

  last = L;
  n ++;

  from[n] = curr;
  onv[n] = L;
  len[n] = len[curr] + 1;
  jump[n][0] = curr;
  for (int j = 1; j < 21; ++ j)
  {
      jump[n][j] = jump[jump[n][j-1]][j-1];
  }
  curr = n;
    g.pb(curr);
}

void UndoCommands(int U)
{
    int sz = g.size()-1;
    curr = g[sz - U];
    g.pb(curr);
}

char GetLetter(int P)
{

    int state = curr;
    int on = state;
    int steps = len[state] - P - 1;
    //cout << curr << " " << len[curr] << " " << P+1 << endl;
   // if(!(len[state] >= P+1))cout << "????" << endl;

    for (int bit = 0; bit < 21; ++ bit)
    {
        if((1 << bit) & steps)state = jump[state][bit];
    }
  return onv[state];

}

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