oj.uz

답안 #130264

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130264 2019-07-14T12:26:42 Z khulegub 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++14
100 / 100
 638 ms 73052 KB 
#include <bits/stdc++.h>
#define pb push_back
#define xx first
#define yy second
#define mp make_pair
using namespace std;

/*
IM RETARDED, JUST SO YOU KNOW LOL.
*/

/*
 
#############################################
# x X x _ P u $ $ y S l a y e r 6 9 _ x X x #
#############################################
 
*/
 
/*
Check array size
Check IO
*/
int sz;
int curr;
vector<pair<char, int> > s; //storing chars and ranks
int node_par[1000005][20]; //nodes parents
int par[1000005]; //cmds parents
vector<int> pos; //storing each cmd's position in "s"
void Init() {
	s.pb(mp('#', 0));
	sz = 0;
	curr = 0; //current cmd is 0
	pos.pb(0); //cmd 0 s position of node is 0
	node_par[0][0] = 0;
	par[0] = 0;
}
void TypeLetter(char L) {
	s.pb(mp(L, s[ pos[curr] ].yy + 1)); //typing letter means new node
	sz++;
	node_par[sz][0] = pos[curr];
	for (int i = 1; i <= 20; i++){
		node_par[sz][i] = node_par[ node_par[sz][i - 1] ][i - 1];
	}
	pos.pb(sz);
	par[++curr] = curr;
}
void UndoCommands(int U) {
	pos.pb(pos[curr - U]);
	par[++curr] = curr - U;
}
char GetLetter(int P) {
	P++;
	int tmp = pos[curr];
	int j = s[tmp].yy - P;
	for (int i = 0; i <= 20; i++ ){
		if ( (j & (1 << i))){
			tmp = node_par[tmp][i];
		}
	}
	return s[tmp].xx;
}

Compilation message

scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:46:6: warning: operation on 'curr' may be undefined [-Wsequence-point]
  par[++curr] = curr;
      ^~~~~~
scrivener.cpp: In function 'void UndoCommands(int)':
scrivener.cpp:50:6: warning: operation on 'curr' may be undefined [-Wsequence-point]
  par[++curr] = curr - U;
      ^~~~~~
scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:43:19: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   node_par[sz][i] = node_par[ node_par[sz][i - 1] ][i - 1];
   ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scrivener.cpp:42:20: note: within this loop
  for (int i = 1; i <= 20; i++){
                  ~~^~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 252 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 510 ms 56096 KB Output is correct
2 Correct 552 ms 62280 KB Output is correct
3 Correct 408 ms 61016 KB Output is correct
4 Correct 393 ms 49488 KB Output is correct
5 Correct 478 ms 59208 KB Output is correct
6 Correct 369 ms 71752 KB Output is correct
7 Correct 418 ms 40048 KB Output is correct
8 Correct 410 ms 55760 KB Output is correct
9 Correct 623 ms 73052 KB Output is correct
10 Correct 240 ms 55620 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 569 ms 48080 KB Output is correct
2 Correct 546 ms 42340 KB Output is correct
3 Correct 379 ms 47048 KB Output is correct
4 Correct 404 ms 35348 KB Output is correct
5 Correct 402 ms 51852 KB Output is correct
6 Correct 384 ms 49328 KB Output is correct
7 Correct 396 ms 52208 KB Output is correct
8 Correct 499 ms 26192 KB Output is correct
9 Correct 638 ms 44380 KB Output is correct
10 Correct 245 ms 55120 KB Output is correct