Submission #439275

#	Time	Username	Problem	Language	Result	Execution time	Memory
439275		prvocislo	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	1092 ms	123992 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5, logn = 20;
struct cmd 
{ 
  bool undo;
  int x, sum;
  vector<int> pv; 
  char c;
};
vector<cmd> v;
void NewCommand() // spracuj ten nakonci v ak vies ze musis ist x znakov dozadu
{
  cmd &c = v.back();
  int x = c.x + 1;
  int pv = v.size() - 1 - x;
  c.pv.assign(logn, 0); 
  if (pv == -1) return;
  c.sum += v[pv].sum;
  if (v[pv].undo) pv = v[pv].pv[0];
  c.pv[0] = pv;
  for (int i = 1; i < logn; i++) c.pv[i] = v[c.pv[i-1]].pv[i-1];
}
void Init() {}
void TypeLetter(char L) 
{
  v.push_back({false, 0, 1, {}, L});
  NewCommand();
}
void UndoCommands(int U) 
{
  v.push_back({true, U, 0, {}, '.'});
  NewCommand();
}
char GetLetter(int P) 
{
  int num = v.back().sum, b = num - P;
  int id = v.size() - 1;
  if (!v[id].undo) b--;
  for (int i = 0; i < logn; i++)
  {
    if ((1 << i) & b) id = v[id].pv[i];
  }
  return v[id].c;
}

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