oj.uz

Submission #952027

# Submission time Handle Problem Language Result Execution time Memory
952027 2024-03-23T03:53:06 Z Yell0 Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 644 ms 101452 KB 
    #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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 820 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 74964 KB Output is correct
2 Correct 528 ms 90264 KB Output is correct
3 Correct 375 ms 87964 KB Output is correct
4 Correct 354 ms 80276 KB Output is correct
5 Correct 417 ms 78524 KB Output is correct
6 Correct 408 ms 101452 KB Output is correct
7 Correct 355 ms 64888 KB Output is correct
8 Correct 374 ms 84872 KB Output is correct
9 Correct 512 ms 96700 KB Output is correct
10 Correct 259 ms 83392 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 73416 KB Output is correct
2 Correct 579 ms 78408 KB Output is correct
3 Correct 344 ms 73440 KB Output is correct
4 Correct 339 ms 70348 KB Output is correct
5 Correct 369 ms 79808 KB Output is correct
6 Correct 372 ms 75964 KB Output is correct
7 Correct 428 ms 81968 KB Output is correct
8 Correct 474 ms 60552 KB Output is correct
9 Correct 644 ms 75256 KB Output is correct
10 Correct 238 ms 82412 KB Output is correct