제출 #952028

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

scrivener

#include <bits/stdc++.h>
 
using namespace std;
struct node {
  vector<int> anc;
  int len;
  char letter;
  int point;
};
vector<node> hist;

void Init() {
  node n;
  n.len = 0;
  n.letter = 0;
  n.point = 0;
  hist.emplace_back(n);
}

void TypeLetter(char L) {
  node n;
  int uidx = hist[hist.size() - 1].point;
  node u = hist[uidx];

  n.letter = L;
  n.len = u.len + 1;
  n.point = hist.size();
  for(int i=0, curr=uidx; 1; ++i) {
    n.anc.emplace_back(curr);
    if(i >= hist[curr].anc.size()) break;
    curr = hist[curr].anc[i];
  }
  hist.emplace_back(n);
}

void UndoCommands(int U) {
  node n;
  n.len = -1;
  n.letter = 0;
  n.point = hist[hist.size() - 1 - U].point;
  hist.emplace_back(n);
}

char GetLetter(int P) {
  int uidx = hist[hist.size() - 1].point;
  node u = hist[uidx];

  int dist = u.len-P-1, curr = uidx;
  for(int i=20; i>=0; --i) {
    if(((1<<i) & dist) == 0) continue;
    curr = hist[curr].anc[i];
  }
  return hist[curr].letter;
}

컴파일 시 표준 에러 (stderr) 메시지

scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:30:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     if(i >= hist[curr].anc.size()) break;
      |        ~~^~~~~~~~~~~~~~~~~~~~~~~~

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