oj.uz

Submission #195707

# Submission time Handle Problem Language Result Execution time Memory
195707 2020-01-16T23:08:19 Z FieryPhoenix Crayfish scrivener (IOI12_scrivener) C++11
100 / 100
 929 ms 90616 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
//#include "scrivener.h"
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
 
int nex;
int length[1000001];
char c[1000001];
int anc[1000001][20];
bool started=false;
int point[1000001];

void calcAnc(int ind){
  for (int i=1;i<=19;i++){
    if (anc[ind][i-1]==-1)
      anc[ind][i]=-1;
    else
      anc[ind][i]=point[anc[point[anc[ind][i-1]]][i-1]];
  }
}
 
void Init(){
  for (int i=0;i<=1000000;i++)
    point[i]=i;
  for (int i=0;i<20;i++)
    anc[0][i]=-1;
}
 
void TypeLetter(char ch){
  if (!started){
    c[0]=ch;
    length[0]=1;
    nex++;
    started=true;
    return;
  }
  length[nex]=length[point[nex-1]]+1;
  c[nex]=ch;
  anc[nex][0]=point[nex-1];
  calcAnc(nex);
  nex++;
}
 
void UndoCommands(int x){
  point[nex]=point[nex-x-1];
  nex++;
}
 
char GetLetter(int ind){
  ind=length[point[nex-1]]-1-ind;
  int cur=nex-1;
  cur=point[cur];
  for (int i=19;i>=0;i--){
    if (((1<<i)&ind)!=0)
      cur=point[anc[cur][i]];
  }
  return c[cur];
}

/*
int main(){
  Init();
  for (;;){
    char c;
    cin>>c;
    if (c=='T'){
      char d; cin>>d;
      TypeLetter(d);
    }
    else if (c=='U'){
      int x; cin>>x;
      UndoCommands(x);
    }
    else{
      int x; cin>>x;
      cout<<GetLetter(x)<<endl;
    }
  }
}
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 63792 KB Output is correct
2 Correct 835 ms 78792 KB Output is correct
3 Correct 529 ms 76536 KB Output is correct
4 Correct 468 ms 79964 KB Output is correct
5 Correct 649 ms 71300 KB Output is correct
6 Correct 607 ms 83248 KB Output is correct
7 Correct 641 ms 71928 KB Output is correct
8 Correct 657 ms 80504 KB Output is correct
9 Correct 819 ms 82032 KB Output is correct
10 Correct 308 ms 90616 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 59100 KB Output is correct
2 Correct 848 ms 51540 KB Output is correct
3 Correct 525 ms 64504 KB Output is correct
4 Correct 465 ms 56480 KB Output is correct
5 Correct 586 ms 74392 KB Output is correct
6 Correct 564 ms 76764 KB Output is correct
7 Correct 590 ms 76792 KB Output is correct
8 Correct 748 ms 65140 KB Output is correct
9 Correct 929 ms 63992 KB Output is correct
10 Correct 315 ms 89480 KB Output is correct