Submission #548708

#	Time	Username	Problem	Language	Result	Execution time	Memory
548708		ikaurov	Crayfish scrivener (IOI12_scrivener)	C++17	60 / 100	1052 ms	83208 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[LOG][N];
int dp[N];
string s = ".";

void Init(){}

void TypeLetter(char c){
  int idx = sz(s);
  dp[idx] = dp[idx - 1] + 1;
  s.pb(c);
  par[0][idx] = idx - 1;
  for (int i = 1; i < LOG; i++) par[i][idx] = par[i - 1][par[i - 1][idx]];
}

void UndoCommands(int x){
  int idx = sz(s);
  dp[idx] = dp[max(idx - 1 - x, 0)];
  s.pb('#');
  par[0][idx] = max(idx - 1 - x, 0);
  for (int i = 1; i < LOG; i++) par[i][idx] = par[i - 1][par[i - 1][idx]];
}

char GetLetter(int pos){
  int cur = sz(s) - 1;
  for (int i = LOG - 1; i >= 0; i--){
    int v = par[i][cur];
    if (dp[v] > pos) cur = v;
  }
  return s[cur];
}

// 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