oj.uz

Submission #251363

# Submission time Handle Problem Language Result Execution time Memory
251363 2020-07-21T02:43:12 Z errorgorn Password (RMI18_password) C++14
100 / 100
 247 ms 528 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int,int>
#define fi first
#define se second

#define rep(x,s,e) for (auto x=s;x!=e;x++)
#define sz(x) (int) (x).size()
#define all(x) (x).begin(),(x).end()

#define si pair<int,string>

priority_queue<si,vector<si>,greater<si> > pq;

int query(string q);

string merge(string i,string j){
	string res=i;
	
	int idx=0;
	
	for (auto &it:j){
		while (true){
			res.insert(idx,1,it);
			
			if (query(res)==sz(res)){
				idx++;
				break;
			}
			
			res.erase(res.begin()+idx);
			idx++;
		}
	}
	
	return res;
}

string guess(int n,int s){
	rep(x,0,s){
		string st;
		rep(y,0,n) st+=(char)('a'+x);
		
		int temp=query(st);
		
		st="";
		rep(y,0,temp) st+=(char)('a'+x);
		
		pq.push(si(temp,st));
	}
	
	while (sz(pq)>1){
		string t1=pq.top().se;pq.pop();
		string t2=pq.top().se;pq.pop();
		
		string ss=merge(t1,t2);
		pq.push(si(sz(ss),ss));
	}
	
	return pq.top().se;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 48 queries.
2 Correct 1 ms 256 KB Guessed the password with 93 queries.
3 Correct 1 ms 256 KB Guessed the password with 91 queries.
4 Correct 2 ms 256 KB Guessed the password with 180 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 376 KB Guessed the password with 2761 queries.
2 Correct 45 ms 384 KB Guessed the password with 5104 queries.
3 Correct 44 ms 376 KB Guessed the password with 4605 queries.
4 Correct 72 ms 504 KB Guessed the password with 8101 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 62 queries.
2 Correct 1 ms 256 KB Guessed the password with 121 queries.
3 Correct 1 ms 256 KB Guessed the password with 48 queries.
4 Correct 1 ms 256 KB Guessed the password with 93 queries.
5 Correct 1 ms 256 KB Guessed the password with 91 queries.
6 Correct 2 ms 256 KB Guessed the password with 180 queries.
7 Correct 26 ms 376 KB Guessed the password with 2761 queries.
8 Correct 45 ms 384 KB Guessed the password with 5104 queries.
9 Correct 44 ms 376 KB Guessed the password with 4605 queries.
10 Correct 72 ms 504 KB Guessed the password with 8101 queries.
11 Correct 86 ms 384 KB Guessed the password with 8178 queries.
12 Correct 84 ms 384 KB Guessed the password with 8184 queries.
13 Correct 105 ms 504 KB Guessed the password with 11549 queries.
14 Correct 122 ms 384 KB Guessed the password with 11679 queries.
15 Correct 104 ms 384 KB Guessed the password with 10910 queries.
16 Correct 104 ms 504 KB Guessed the password with 10880 queries.
17 Correct 107 ms 376 KB Guessed the password with 10245 queries.
18 Correct 101 ms 504 KB Guessed the password with 10274 queries.
19 Correct 102 ms 384 KB Guessed the password with 9709 queries.
20 Correct 96 ms 504 KB Guessed the password with 9801 queries.
21 Correct 117 ms 384 KB Guessed the password with 11743 queries.
22 Correct 110 ms 504 KB Guessed the password with 11781 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 62 queries.
2 Correct 1 ms 256 KB Guessed the password with 121 queries.
3 Correct 1 ms 256 KB Guessed the password with 48 queries.
4 Correct 1 ms 256 KB Guessed the password with 93 queries.
5 Correct 1 ms 256 KB Guessed the password with 91 queries.
6 Correct 2 ms 256 KB Guessed the password with 180 queries.
7 Correct 26 ms 376 KB Guessed the password with 2761 queries.
8 Correct 45 ms 384 KB Guessed the password with 5104 queries.
9 Correct 44 ms 376 KB Guessed the password with 4605 queries.
10 Correct 72 ms 504 KB Guessed the password with 8101 queries.
11 Correct 86 ms 384 KB Guessed the password with 8178 queries.
12 Correct 84 ms 384 KB Guessed the password with 8184 queries.
13 Correct 105 ms 504 KB Guessed the password with 11549 queries.
14 Correct 122 ms 384 KB Guessed the password with 11679 queries.
15 Correct 104 ms 384 KB Guessed the password with 10910 queries.
16 Correct 104 ms 504 KB Guessed the password with 10880 queries.
17 Correct 107 ms 376 KB Guessed the password with 10245 queries.
18 Correct 101 ms 504 KB Guessed the password with 10274 queries.
19 Correct 102 ms 384 KB Guessed the password with 9709 queries.
20 Correct 96 ms 504 KB Guessed the password with 9801 queries.
21 Correct 117 ms 384 KB Guessed the password with 11743 queries.
22 Correct 110 ms 504 KB Guessed the password with 11781 queries.
23 Correct 224 ms 448 KB Guessed the password with 23751 queries.
24 Correct 198 ms 452 KB Guessed the password with 21005 queries.
25 Correct 225 ms 520 KB Guessed the password with 23741 queries.
26 Correct 139 ms 400 KB Guessed the password with 19118 queries.
27 Correct 247 ms 528 KB Guessed the password with 23712 queries.
28 Correct 168 ms 500 KB Guessed the password with 16852 queries.
29 Correct 208 ms 516 KB Guessed the password with 23732 queries.
30 Correct 152 ms 400 KB Guessed the password with 14420 queries.