Submission #751731

#	Time	Username	Problem	Language	Result	Execution time	Memory
751731		allin27x	Crayfish scrivener (IOI12_scrivener)	C++17	0 / 100	150 ms	19232 KiB

scrivener

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

const int n = (int)1e6+2;
int sgt[2*n]={0};
int op = 0;
char ch[n];
string res = "";
int undo[n]={0};
bool undid = 0;

void update(int l, int r){
	for (l+=n, r+=n+1; l<r; l>>=1, r>>=1){
		if (l&1) sgt[l--] ^= 1;
		if (r&1) sgt[--r] ^= 1;
	}
}

int get(int a){
	int res = 0;
	for (a+=n; a>=1; a>>=1) res ^= sgt[a];
	return res;
}

void undoOper(){
	for (int i=n-1; i>=0; --i){
		if (!undo[i] || !get(i)) continue;
		update(i-undo[i], i-1);
		sgt[i] = 0;
	}
	for (int i=0; i<n; i++){
		if (sgt[i]) res+=ch[i];
	}
}
void Init(){return;}

void TypeLetter(char L){
	ch[op] = L;
	sgt[n+op] = 1;
	op++;
}

void UndoCommands(int U){
	sgt[n+op] = 1;
	undo[op] = U;
	op++;
}

char GetLetter(int P){
	if (!undid) {undid = 1; undoOper();}
	return res[P];
}

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