Submission #958566

#	Time	Username	Problem	Language	Result	Execution time	Memory
958566		PoPularPlusPlus	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	1055 ms	201768 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define vf first 
#define vs second

const int N = 1000005;
const int L = 25;
vector<char> v[N];
vector<pair<int,int>> val;
vector<vector<pair<int,int>>> up[N];

void Init(){
	val.pb(mp(-1,0));
}

void TypeLetter(char c){
	int pos = val.back().vf + 1;
	pair<int,int> cur = val.back();
	v[pos].pb(c);
	val.pb(mp(pos , v[pos].size()-1));
	vector<pair<int,int>> x;
	x.pb(cur);
	for(int i = 1; i < L; i++){
		if(cur.vf == -1){
			x.pb(mp(-1,0));
		}
		else {
			x.pb(up[cur.vf][cur.vs][i-1]);
			cur = up[cur.vf][cur.vs][i-1];
		}
	}
	up[pos].pb(x);
}

void UndoCommands(int u){
	val.pb(val[val.size()-u-1]);
}

char GetLetter(int p){
	pair<int,int> cur = val.back();
	for(int i = L-1; i > 0; i--){
		if(up[cur.vf][cur.vs][i-1].vf > p){
			cur = up[cur.vf][cur.vs][i-1];
		}
	}
	if(p!=cur.vf)cur = up[cur.vf][cur.vs][0];
	//cout << cur.vf << ' ' << cur.vs << endl;
	return v[cur.vf][cur.vs];
}
/*
int 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;

}
*/

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