제출 #1000439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1000439		jer033	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++17	100 / 100	656 ms	136692 KiB

scrivener

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

vector<vector<int>> stac;

void Init() {
  vector<int> initial(23, 0);
  stac.push_back(initial);
}

void TypeLetter(char L) {
  int x = stac.size();
  vector<int> newstac;
  newstac.push_back(stac[x-1][0]+1);
  newstac.push_back(L-'a');
  int curr = x-1;
  for (int i=2; i<=22; i++)
  {
    newstac.push_back(curr);
    curr = stac[curr][i];
  }
  stac.push_back(newstac);
}

void UndoCommands(int U) {
  int curr = stac.size() - 1;
  stac.push_back(stac[curr-U]);
}

char GetLetter(int P) {
  int height = stac.size();
  int text_length = stac[height-1][0];
  int akyat = text_length-1-P;
  int curr = height-1;
  for (int i=20; i>=0; i--)
  {
    if (akyat>=(1<<i))
    {
      akyat -= (1<<i);
      curr = stac[curr][i+2];
    }
  }
  char ans = ('a'+stac[curr][1]);
  return ans;
}

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