oj.uz

Submission #251364

# Submission time Handle Problem Language Result Execution time Memory
251364 2020-07-21T03:35:31 Z oolimry Password (RMI18_password) C++14
100 / 100
 624 ms 812 KB 
#include <bits/stdc++.h>
using namespace std;
int query(string q);
int cur;
string guess(int n, int s){
	
	vector<char> chars;
	for(int i = 0;i < s;i++) chars.push_back('a' + i);
	
	string tree[2*s];
	
	for(int i = 0;i < s;i++){
		string S = "";
		int pre = 0;
		while(true){
			S += chars[i];
			cur = query(S);
			if(pre == cur) break;
			pre = cur;
		}
		S.pop_back();
		tree[s+i] = S;
	}
	
	
	for(int i = s-1;i >= 1;i--){
		string L = tree[i<<1]; string R = tree[i<<1|1];
		
		int cnt = R.size();
		vector<int> pos[R.size()+1];
		
		int p = 0;		
		for(int l = 0;l < (int) L.size();){
			string S;
			if(p == (int) R.size()){
				for(int j = l;j < (int) L.size();j++) pos[p].push_back(j);
				break;
			}
			cnt++;
			
			pos[p].push_back(l);
			
			for(int j = 0;j < (int) R.size();j++){
				for(int c : pos[j]){
					S += L[c];
				}
				S += R[j];
			}
			
			cur = query(S);
			//cout << cnt << "\n";
			if(cur != cnt){
				pos[p].pop_back();
				p++;
				cnt--;
			}
			else{
				l++;
			}			
		}
		
		string S;
					
		for(int j = 0;j <= (int) R.size();j++){
			for(int c : pos[j]){
				S += L[c];
			}
			if(j != (int) R.size()) S += R[j];
		}
		
		//cout << i << " " << S << "\n";
		tree[i] = S;
	}
	
	
	
	return tree[1];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 73 queries.
2 Correct 1 ms 256 KB Guessed the password with 125 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 99 queries.
2 Correct 2 ms 256 KB Guessed the password with 160 queries.
3 Correct 2 ms 256 KB Guessed the password with 260 queries.
4 Correct 3 ms 256 KB Guessed the password with 297 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 392 KB Guessed the password with 4824 queries.
2 Correct 91 ms 380 KB Guessed the password with 6335 queries.
3 Correct 111 ms 632 KB Guessed the password with 8287 queries.
4 Correct 149 ms 632 KB Guessed the password with 10788 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 73 queries.
2 Correct 1 ms 256 KB Guessed the password with 125 queries.
3 Correct 1 ms 256 KB Guessed the password with 99 queries.
4 Correct 2 ms 256 KB Guessed the password with 160 queries.
5 Correct 2 ms 256 KB Guessed the password with 260 queries.
6 Correct 3 ms 256 KB Guessed the password with 297 queries.
7 Correct 75 ms 392 KB Guessed the password with 4824 queries.
8 Correct 91 ms 380 KB Guessed the password with 6335 queries.
9 Correct 111 ms 632 KB Guessed the password with 8287 queries.
10 Correct 149 ms 632 KB Guessed the password with 10788 queries.
11 Correct 289 ms 660 KB Guessed the password with 14165 queries.
12 Correct 304 ms 504 KB Guessed the password with 14625 queries.
13 Correct 356 ms 500 KB Guessed the password with 15981 queries.
14 Correct 235 ms 596 KB Guessed the password with 17573 queries.
15 Correct 311 ms 504 KB Guessed the password with 16408 queries.
16 Correct 323 ms 432 KB Guessed the password with 18514 queries.
17 Correct 351 ms 608 KB Guessed the password with 16606 queries.
18 Correct 292 ms 516 KB Guessed the password with 18577 queries.
19 Correct 341 ms 684 KB Guessed the password with 16707 queries.
20 Correct 331 ms 688 KB Guessed the password with 19049 queries.
21 Correct 322 ms 812 KB Guessed the password with 17984 queries.
22 Correct 337 ms 760 KB Guessed the password with 18906 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 73 queries.
2 Correct 1 ms 256 KB Guessed the password with 125 queries.
3 Correct 1 ms 256 KB Guessed the password with 99 queries.
4 Correct 2 ms 256 KB Guessed the password with 160 queries.
5 Correct 2 ms 256 KB Guessed the password with 260 queries.
6 Correct 3 ms 256 KB Guessed the password with 297 queries.
7 Correct 75 ms 392 KB Guessed the password with 4824 queries.
8 Correct 91 ms 380 KB Guessed the password with 6335 queries.
9 Correct 111 ms 632 KB Guessed the password with 8287 queries.
10 Correct 149 ms 632 KB Guessed the password with 10788 queries.
11 Correct 289 ms 660 KB Guessed the password with 14165 queries.
12 Correct 304 ms 504 KB Guessed the password with 14625 queries.
13 Correct 356 ms 500 KB Guessed the password with 15981 queries.
14 Correct 235 ms 596 KB Guessed the password with 17573 queries.
15 Correct 311 ms 504 KB Guessed the password with 16408 queries.
16 Correct 323 ms 432 KB Guessed the password with 18514 queries.
17 Correct 351 ms 608 KB Guessed the password with 16606 queries.
18 Correct 292 ms 516 KB Guessed the password with 18577 queries.
19 Correct 341 ms 684 KB Guessed the password with 16707 queries.
20 Correct 331 ms 688 KB Guessed the password with 19049 queries.
21 Correct 322 ms 812 KB Guessed the password with 17984 queries.
22 Correct 337 ms 760 KB Guessed the password with 18906 queries.
23 Correct 624 ms 532 KB Guessed the password with 28713 queries.
24 Correct 535 ms 672 KB Guessed the password with 28260 queries.
25 Correct 538 ms 724 KB Guessed the password with 28695 queries.
26 Correct 600 ms 748 KB Guessed the password with 27412 queries.
27 Correct 562 ms 708 KB Guessed the password with 28808 queries.
28 Correct 536 ms 632 KB Guessed the password with 27153 queries.
29 Correct 585 ms 700 KB Guessed the password with 28868 queries.
30 Correct 616 ms 512 KB Guessed the password with 27172 queries.