Submission #952027

#	Time	Username	Problem	Language	Result	Execution time	Memory
952027		Yell0	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	644 ms	101452 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=25; i>=0; --i) {
        if(((1<<i) & dist) == 0) continue;
        curr = hist[curr].anc[i];
      }
      return hist[curr].letter;
    }

Compilation message (stderr)

scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:30:14: 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