Submission #851277

#	Time	Username	Problem	Language	Result	Execution time	Memory
851277		Halym2007	Crayfish scrivener (IOI12_scrivener)	C++11	100 / 100	330 ms	70280 KiB

scrivener

//#include "scrivener.h"
#include <bits/stdc++.h>
using namespace std;
#define sz size()
#define pb push_back
const int MAXM = 1e6 + 5;
const int LOG = 20;
#define ff first
#define ss second
#define ll long long
string s;
vector <int> v;
int tr, idx, pr, P[MAXM][LOG], lvl[MAXM];
char val[MAXM];
void Init() {
	return;
}
void TypeLetter(char L) {
	idx++;
	val[idx] = L;
	P[idx][0] = pr;
	lvl[idx] = lvl[pr] + 1;
	v.pb (idx);
	pr = idx;
	for (int j = 1; j < LOG; ++j) {
		if (P[idx][j - 1]) {
			P[idx][j] = P[P[idx][j - 1]][j - 1];
		}
	}
}
void UndoCommands(int U) {
	pr = v[(int)v.sz - U - 1];
	v.pb (pr);
}

char GetLetter(int PP) {
	int san = lvl[pr] - (PP + 1);
	int jog = pr;
	for (int i = LOG - 1; i >= 0; i--) {
		if (san>>i&1) {
			jog = P[jog][i];
		}
	}	
	return val[jog];
}


//#include <stdlib.h>
//#include <stdio.h>
//#include <assert.h>
//
//#define inbuf_len 1 << 16
//#define outbuf_len 1 << 16
//
//
//int main() {
////	Typeletter ('a');
////	return 0;
//	freopen ("input.txt", "r", stdin);
//  int tmp;
//
//  /* Set input and output buffering */
//  char *inbuf, *outbuf;
//  inbuf = (char*) malloc(inbuf_len * sizeof(char));
//  outbuf = (char*) malloc(outbuf_len * sizeof(char));
//  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
//  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
//
//  Init();
//
//  int cmd_num;
//  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", letter);
//    }
//  }
//
//  printf("\n");
//  return 0;
//
//}

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