oj.uz

Submission #952028

# Submission time Handle Problem Language Result Execution time Memory
952028 2024-03-23T03:55:01 Z Yell0 Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 618 ms 95648 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=20; 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: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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
6 Correct 1 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 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 604 KB Output is correct
2 Correct 1 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 872 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 856 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 437 ms 76268 KB Output is correct
2 Correct 481 ms 86204 KB Output is correct
3 Correct 393 ms 84020 KB Output is correct
4 Correct 350 ms 74428 KB Output is correct
5 Correct 403 ms 74684 KB Output is correct
6 Correct 405 ms 95648 KB Output is correct
7 Correct 345 ms 58540 KB Output is correct
8 Correct 365 ms 78768 KB Output is correct
9 Correct 504 ms 92872 KB Output is correct
10 Correct 246 ms 79292 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 73736 KB Output is correct
2 Correct 572 ms 75180 KB Output is correct
3 Correct 334 ms 69220 KB Output is correct
4 Correct 343 ms 66500 KB Output is correct
5 Correct 363 ms 75452 KB Output is correct
6 Correct 363 ms 72352 KB Output is correct
7 Correct 400 ms 76816 KB Output is correct
8 Correct 453 ms 55148 KB Output is correct
9 Correct 618 ms 70840 KB Output is correct
10 Correct 241 ms 79032 KB Output is correct