Submission #575792

#	Time	Username	Problem	Language	Result	Execution time	Memory
575792		arneves	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	507 ms	93428 KiB

scrivener

/*
	  ______  _____  _______ _     _ _______ __   _  _____  _  _  _
	 |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
	 |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
	
	
	       .      .           .      .           .      .    	
	       _\/  \/_           _\/  \/_           _\/  \/_    	
	        _\/\/_             _\/\/_             _\/\/_     	
	    _\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 	
	     / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  	
	        _/\/\_             _/\/\_             _/\/\_     	
	        /\  /\             /\  /\             /\  /\     	
	       '      '           '      '           '      '    	
	
*/
 
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
 
using namespace std;
 
/*using ll = long long;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
*/
const int LOG=21;
const int MX=1e6+5;

struct no{
	char c;
	int pai[LOG];
	int profundidade;
};

int tempo;
no vv[MX];


void imprimir(){
	for(int i=0; i<tempo+1; i++){
		cout<<"->"<<vv[i].c<<' '<<vv[i].pai[0]<<' ';
	}
	cout<<'\n';
}

void Init(){
	tempo=0;
	//raiz
	vv[0].c='#';
	for(int i=0; i<LOG; i++){
		vv[0].pai[i]=0;
	}
	vv[0].profundidade=0;
	//imprimir();
}

void TypeLetter(char L){
	tempo++;
	vv[tempo].c=L;
	vv[tempo].pai[0]=tempo-1;
	for(int i=1; i<LOG; i++){
		vv[tempo].pai[i]=vv[vv[tempo].pai[i-1]].pai[i-1];
	}
	vv[tempo].profundidade=vv[tempo-1].profundidade+1;
	//imprimir();
}

void UndoCommands(int U) {
	tempo++;
	vv[tempo]=vv[tempo-U-1];
	//imprimir();
}

char GetLetter(int P) {
	int x=vv[tempo].profundidade-P-1;
	int pos=tempo;
	for(int i=0; i<LOG; i++){
		if(x&(1<<i)) pos=vv[pos].pai[i];
	}
	return vv[pos].c;
	//imprimir();
}

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