Submission #548721

#	Time	Username	Problem	Language	Result	Execution time	Memory
548721		ikaurov	Crayfish scrivener (IOI12_scrivener)	C++17	60 / 100	1004 ms	87032 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], lg[N];
int dp[N];
string s = ".";
 
void Init(){
  lg[1] = 0;
  for (int i = 2; i < N; i++) lg[i] = lg[i >> 1] + 1;
}
 
void TypeLetter(char c){
  int idx = sz(s);
  dp[idx] = dp[idx - 1] + 1;
  s.pb(c);
  par[idx][0] = idx - 1;
  for (int i = 1; i < LOG; i++){
    par[idx][i] = par[par[idx][i - 1]][i - 1];
    if (!par[idx][i]) break;
  }
}
 
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);
  for (int i = 1; i < LOG; i++){
    par[idx][i] = par[par[idx][i - 1]][i - 1];
    if (!par[idx][i]) break;
  }
}
 
char GetLetter(int pos){
  int idx = sz(s) - 1;
  for (int i = lg[sz(s)]; i >= 0; 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