제출 #1012519

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

scrivener

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
const ll mxN = 1e6 + 5;
const ll mod = 1e9 + 7;
const int inf = 2e9;
using namespace std;
int id = -1;
pair<int,char> a[mxN];
int st[mxN][25];
void Init() {
}

void TypeLetter(char L) {
  id++;
  if(!id) a[id] = {0,L};
  else a[id] = {a[id - 1].F + 1,L};
  if(id) st[id][0] = id - 1;
  for(int pw = 1;pw < 21;pw++){
    st[id][pw] = st[st[id][pw - 1]][pw - 1];
  }
}
void UndoCommands(int U) {
  id++;
  if(id <= U) a[id] = {-1,'#'};
  else a[id] = a[id - U - 1];
  if(id > U) st[id][0] = id - U - 1;
  for(int pw = 1;pw < 21;pw++){
    st[id][pw] = st[st[id][pw - 1]][pw - 1];
  }
}

char GetLetter(int P) {
  // cout<<a[id].F<<' '<<a[id].S<<'\n';
  int i = id;
  for(int pw = 20;pw >= 0;pw--){
    if(a[st[i][pw]].F >= P){
      i = st[i][pw];
    }
  }
  return a[i].S;
}

#ifdef EMAD
int main() {
  Init();

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

}
#endif

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