Submission #548716

#	Time	Username	Problem	Language	Result	Execution time	Memory
548716		ikaurov	Crayfish scrivener (IOI12_scrivener)	C++17	60 / 100	1074 ms	87120 KiB

scrivener

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) int((x).size())
#define fi first
#define se second
#define endl '\n'
 
const int N = 1e6 + 20, LOG = 20;
 
int par[N][LOG], cur[N];
int dp[N];
string s = ".";
 
void Init(){
  cur[0] = LOG;
}
 
void TypeLetter(char c){
  int idx = sz(s);
  dp[idx] = dp[idx - 1] + 1;
  s.pb(c);
  par[idx][0] = idx - 1;
  cur[idx] = 1;
}
 
void UndoCommands(int x){
  int idx = sz(s);
  dp[idx] = dp[max(idx - 1 - x, 0)];
  s.pb('#');
  par[idx][0] = max(idx - 1 - x, 0);
  cur[idx] = 1;
}

void calc(int idx, int i){
  while (cur[idx] <= i){
    int x = par[idx][cur[idx] - 1];
    if (!x){
      cur[idx] = LOG;
      break;
    }
    calc(x, cur[idx] - 1);
    par[idx][cur[idx]] = par[x][cur[idx] - 1], cur[idx]++;
  }
}
 
char GetLetter(int pos){
  int idx = sz(s) - 1;
  for (int i = LOG - 1; i >= 0; i--){
    calc(idx, i);
    if (dp[par[idx][i]] > pos) idx = par[idx][i];
  }
  return s[idx];
}
 
// signed main(){
//   ios_base::sync_with_stdio(0);
//   cin.tie(0);
//   // cout.precision(20);
//   Init();
//   TypeLetter('a');
//   TypeLetter('b');
//   GetLetter(1);
//   TypeLetter('d');
//   UndoCommands(2);
//   UndoCommands(1);
//   GetLetter(2);
//   TypeLetter('e');
//   UndoCommands(1);
//   UndoCommands(5);
//   TypeLetter('c');
//   GetLetter(2);
//   UndoCommands(2);
//   GetLetter(2);
// }

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