oj.uz

Submission #119959

# Submission time Handle Problem Language Result Execution time Memory
119959 2019-06-22T18:16:21 Z dolphingarlic Crayfish scrivener (IOI12_scrivener) C++14
12 / 100
 1000 ms 12204 KB 
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

char T[1000001];
int dad[1000001], dadH[1000001], H[1000001];
vector<int> v;
int act, it;

void Init() {
  it = 1;
  act = 0;
  H[0] = -1;
  dad[0] = dadH[0] = 0;
  v.clear();
}

void TypeLetter(char L) {
  T[it] = L;
  H[it] = H[act]+1;
  dad[it] = act;
  if(H[it] % 1000 == 0) //sqrt(1000000) => 1000
    dadH[it] = it;
  else
    dadH[it] = dadH[act];
  v.push_back(it);
  act = it++;
}

void UndoCommands(int U) {
  act = v[v.size() - U - 1];
  v.push_back(act);
}

char GetLetter(int P) { // O(sqrt(height))
  int i = act;
  while(H[ dadH[i] ] > P) i = dadH[i];// O(sqrt(height))
  while(H[ dad[i] ] >= P) i = dad[i]; // O(sqrt(height))
  return T[i];
}

// int main() {
//   int t;
//   cin >> t;
//   Init();
//   for (int i = 0; i < t; i++) {
//     char c, d; int e;
//     cin >> c;
//     switch (c) {
//       case 'T':
//         cin >> d;
//         TypeLetter(d);
//         break;
//       case 'P':
//         cin >> e;
//         cout << GetLetter(e) << '\n';
//         break;
//       default:
//         cin >> e;
//         UndoCommands(e);
//     }
//   }
// }

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 440 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Execution timed out 1080 ms 384 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 12204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 1588 KB Time limit exceeded
2 Halted 0 ms 0 KB -