oj.uz

Submission #121665

# Submission time Handle Problem Language Result Execution time Memory
121665 2019-06-26T23:40:39 Z Lawliet Crayfish scrivener (IOI12_scrivener) C++14
5 / 100
 395 ms 66040 KB 
#include <bits/stdc++.h>
 
#define LOG 22
#define MAX 1000010
 
using namespace std;
 
class PersistentStack
{
	public:
		
		void add(char s)
		{
			curNode++;
			curVersion++;
			
			curTop = curNode;
			
			v[curNode] = s;
			version[curVersion] = curNode;
			dp[0][curNode] = version[curVersion - 1];
			prof[curNode] = prof[ dp[0][curNode] ] + 1;
						
			for(int k = 1 ; k < LOG ; k++)
			{
				int jump = dp[k - 1][curNode];
				dp[k][curNode] = dp[k - 1][jump];
			}
		}
		
		void back(int k)
		{
			curVersion++;
			
			version[curVersion] = version[curVersion - k - 1];
			
			curTop = version[ curVersion ];
		}
		
		char query(int k)
		{
			int d = prof[curNode] - k;
			int cur = curTop;
			
			for(int g = 0 ; g < LOG ; g++)
				if(d & (1 << g)) cur = dp[g][cur];
					
			return v[cur];
		}
		
	private:
		
		int curTop;
		int curNode;
		int curVersion;
		
		int prof[MAX];
		int dp[LOG][MAX];
		int version[MAX];
		
		char v[MAX];
};
 
PersistentStack p;
 
void Init() { }
 
void TypeLetter(char L) { p.add( L ); }
 
void UndoCommands(int U) { p.back( U ); }
 
char GetLetter(int P) { return p.query( P + 1 ); }

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 59892 KB Output is correct
2 Correct 358 ms 66040 KB Output is correct
3 Correct 326 ms 65448 KB Output is correct
4 Incorrect 324 ms 54520 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 395 ms 52280 KB Output isn't correct
2 Halted 0 ms 0 KB -