oj.uz

Submission #851277

# Submission time Handle Problem Language Result Execution time Memory
851277 2023-09-19T09:28:03 Z Halym2007 Crayfish scrivener (IOI12_scrivener) C++11
100 / 100
 330 ms 70280 KB 
//#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 59384 KB Output is correct
2 Correct 230 ms 63684 KB Output is correct
3 Correct 213 ms 64080 KB Output is correct
4 Correct 215 ms 53184 KB Output is correct
5 Correct 217 ms 55832 KB Output is correct
6 Correct 195 ms 67912 KB Output is correct
7 Correct 193 ms 38004 KB Output is correct
8 Correct 193 ms 54344 KB Output is correct
9 Correct 258 ms 70280 KB Output is correct
10 Correct 145 ms 53312 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 52376 KB Output is correct
2 Correct 263 ms 49096 KB Output is correct
3 Correct 191 ms 51900 KB Output is correct
4 Correct 209 ms 42744 KB Output is correct
5 Correct 192 ms 53512 KB Output is correct
6 Correct 201 ms 51484 KB Output is correct
7 Correct 201 ms 55812 KB Output is correct
8 Correct 315 ms 30144 KB Output is correct
9 Correct 330 ms 48224 KB Output is correct
10 Correct 145 ms 53132 KB Output is correct