Submission #382341

#	Time	Username	Problem	Language	Result	Execution time	Memory
382341		mehrdad_sohrabi	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	551 ms	92524 KiB

scrivener

#include <bits/stdc++.h>
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=1e6+100,M=22;
ll par[N][M];
char c[N];
ll sz[N];
char last[N];
void mrg(ll u,ll v,bool b){
    if (b==0){
        sz[u]=sz[v];
        last[u]=last[v];
        for (int i=0;i<M;i++) par[u][i]=par[v][i];
    }
    else{
        sz[u]=sz[v]+1;
        last[u]=c[u];
        par[u][0]=v;
    //    cout << v << " eorijto4rj " << endl;
        for (int i=1;i<M;i++) par[u][i]=par[par[u][i-1]][i-1];
    }
    return ;
}
ll get(ll v,ll h){
    for (int i=0;i<M;i++){
        if ((h & (1<<i))) v=par[v][i];
    }
    return v;
}
void Init(){
    return ;
}
ll cnt=0;
vector <char> dd;
void TypeLetter(char L) {
    cnt++;
    c[cnt]=L;
    mrg(cnt,cnt-1,1);
   // cout << last[cnt] << endl;
}

void UndoCommands(int U) {
    cnt++;
    mrg(cnt,cnt-U-1,0);
}

char GetLetter(int P) {
    ll zz=P;
    P=sz[cnt]-P;
    P--;
   // cout << P << endl;
    if (P==0) return last[cnt];
    ll z=get(cnt,P);
  //  cout << z << endl;
  //  if (dd[zz]!=c[z]) cout << "GOOZ" << endl;
    return last[z];
}
/*
int32_t main(){
    Init();

  int cmd_num;
int   tmp = scanf("%d", &cmd_num);
  assert(tmp == 1);

  int i;
  for (i = 0; i < cmd_num; i++) {
    char cmd;
    tmp = scanf(" %c", &cmd);
    assert(tmp == 1);
    if (cmd == 'T') {
      char letter;
      tmp = scanf(" %c", &letter);
      assert(tmp == 1);
      TypeLetter(letter);
    }
    else if (cmd == 'U') {
      int number;
      tmp = scanf("%d", &number);
      assert(tmp == 1);
      UndoCommands(number);
    }
    else if (cmd == 'P') {
      int index;
      char letter;
      tmp = scanf("%d", &index);
      assert(tmp == 1);
      letter = GetLetter(index);
      printf("%c\n", letter);
    }
  }

  puts("Let's test for cheating!!");

  return 0;
}

*/

Compilation message (stderr)

scrivener.cpp: In function 'char GetLetter(int)':
scrivener.cpp:60:8: warning: unused variable 'zz' [-Wunused-variable]
   60 |     ll zz=P;
      |        ^~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40