oj.uz

Submission #342334

# Submission time Handle Problem Language Result Execution time Memory
342334 2021-01-01T22:44:03 Z Gajowy Password (RMI18_password) C++14
80 / 100
 867 ms 748 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string str);

string guess(int n,int s){
	string res;
	string qs;
	for(int cc=0;cc<s;cc++){
		char c=(char)('a'+cc);
		qs.clear();
		if(res.size()==0){
			for(int i=0;i<n;i++)
				qs.push_back(c);
			int qres=query(qs);
			for(int i=0;i<qres;i++)
				res.push_back(c);
		}
		else
		if((int)res.size()<n){
			for(int i=0;i<n-(int)res.size();i++)
				qs.push_back(c);
			int qres=query(qs);
			if(qres==0)
				continue;
			vector<int> pos;
			for(int l=1;l<=qres;l++){
				int lo=0,hi=res.size();
				while(lo<hi){
					qs.clear();
					int mid=(lo+hi)/2+1;
					for(int i=0;i<mid;i++)
						qs.push_back(res[i]);
					for(int i=0;i<l;i++)
						qs.push_back(c);
					int smqres=query(qs);
					if(smqres==(int)qs.size())
						lo=mid;
					else
						hi=mid-1;
				}
				pos.push_back(lo);
				//cerr<<lo<<'\n';
			}
			reverse(begin(pos),end(pos));
			string new_res;
			for(int i=res.size();i>=0;i--){
				while(pos.size()>0&&pos.back()>=i)
					new_res.push_back(c),pos.pop_back();
				if(i!=0)
					new_res.push_back(res[i-1]);
			}
			reverse(begin(new_res),end(new_res));
			res=new_res;
		}
	}
	return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 56 queries.
2 Correct 2 ms 364 KB Guessed the password with 101 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Guessed the password with 129 queries.
2 Correct 2 ms 364 KB Guessed the password with 134 queries.
3 Correct 3 ms 364 KB Guessed the password with 322 queries.
4 Correct 5 ms 364 KB Guessed the password with 429 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 492 KB Guessed the password with 7860 queries.
2 Correct 134 ms 492 KB Guessed the password with 10916 queries.
3 Correct 223 ms 492 KB Guessed the password with 13619 queries.
4 Correct 287 ms 516 KB Guessed the password with 18481 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 56 queries.
2 Correct 2 ms 364 KB Guessed the password with 101 queries.
3 Correct 2 ms 364 KB Guessed the password with 129 queries.
4 Correct 2 ms 364 KB Guessed the password with 134 queries.
5 Correct 3 ms 364 KB Guessed the password with 322 queries.
6 Correct 5 ms 364 KB Guessed the password with 429 queries.
7 Correct 70 ms 492 KB Guessed the password with 7860 queries.
8 Correct 134 ms 492 KB Guessed the password with 10916 queries.
9 Correct 223 ms 492 KB Guessed the password with 13619 queries.
10 Correct 287 ms 516 KB Guessed the password with 18481 queries.
11 Correct 287 ms 492 KB Guessed the password with 22728 queries.
12 Correct 451 ms 748 KB Guessed the password with 27189 queries.
13 Correct 497 ms 492 KB Guessed the password with 27527 queries.
14 Correct 371 ms 544 KB Guessed the password with 29647 queries.
15 Correct 513 ms 748 KB Guessed the password with 28406 queries.
16 Correct 430 ms 492 KB Guessed the password with 31690 queries.
17 Correct 417 ms 620 KB Guessed the password with 28219 queries.
18 Correct 524 ms 624 KB Guessed the password with 33024 queries.
19 Correct 482 ms 748 KB Guessed the password with 27682 queries.
20 Correct 551 ms 504 KB Guessed the password with 33811 queries.
21 Correct 471 ms 516 KB Guessed the password with 31293 queries.
22 Correct 478 ms 620 KB Guessed the password with 35530 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 56 queries.
2 Correct 2 ms 364 KB Guessed the password with 101 queries.
3 Correct 2 ms 364 KB Guessed the password with 129 queries.
4 Correct 2 ms 364 KB Guessed the password with 134 queries.
5 Correct 3 ms 364 KB Guessed the password with 322 queries.
6 Correct 5 ms 364 KB Guessed the password with 429 queries.
7 Correct 70 ms 492 KB Guessed the password with 7860 queries.
8 Correct 134 ms 492 KB Guessed the password with 10916 queries.
9 Correct 223 ms 492 KB Guessed the password with 13619 queries.
10 Correct 287 ms 516 KB Guessed the password with 18481 queries.
11 Correct 287 ms 492 KB Guessed the password with 22728 queries.
12 Correct 451 ms 748 KB Guessed the password with 27189 queries.
13 Correct 497 ms 492 KB Guessed the password with 27527 queries.
14 Correct 371 ms 544 KB Guessed the password with 29647 queries.
15 Correct 513 ms 748 KB Guessed the password with 28406 queries.
16 Correct 430 ms 492 KB Guessed the password with 31690 queries.
17 Correct 417 ms 620 KB Guessed the password with 28219 queries.
18 Correct 524 ms 624 KB Guessed the password with 33024 queries.
19 Correct 482 ms 748 KB Guessed the password with 27682 queries.
20 Correct 551 ms 504 KB Guessed the password with 33811 queries.
21 Correct 471 ms 516 KB Guessed the password with 31293 queries.
22 Correct 478 ms 620 KB Guessed the password with 35530 queries.
23 Incorrect 867 ms 728 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -