oj.uz

Submission #709190

# Submission time Handle Problem Language Result Execution time Memory
709190 2023-03-13T07:42:45 Z zaneyu Password (RMI18_password) C++14
100 / 100
 341 ms 680 KB 
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=500+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e8+7;
const ld PI=acos(-1);
const ld eps=1e-4;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
int query(string s);
string merge(string a,string b){
	int n=sz(a),m=sz(b);
	int pa=0,pb=0;
	string ans="";
	while(pa<n and pb<m){
		string cur=ans;
		cur.pb(a[pa]);
		for(int i=pb;i<m;i++) cur.pb(b[i]);
		if(query(cur)==sz(cur)){
			ans.pb(a[pa++]);
		}
		else ans.pb(b[pb++]);
	}
	while(pa<n) ans.pb(a[pa++]);
	while(pb<m) ans.pb(b[pb++]);
	return ans;
}
string guess(int n, int s){
	set<pair<int,string>> ss;
	REP(i,s){
		string z="";
		REP(a,n) z.pb(i+'a');
		string ans="";
		int k=query(z);
		REP(a,k) ans.pb(i+'a');
		ss.insert({k,ans});
	}
	while(sz(ss)>1){
		auto a=(*ss.begin()).s;
		ss.erase(ss.begin());
		auto b=(*ss.begin()).s;
		ss.erase(ss.begin());
		string x=merge(a,b);
		ss.insert({sz(x),x});
	}
	return (*ss.begin()).s;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 58 queries.
2 Correct 1 ms 208 KB Guessed the password with 103 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 49 queries.
2 Correct 1 ms 208 KB Guessed the password with 90 queries.
3 Correct 1 ms 208 KB Guessed the password with 92 queries.
4 Correct 2 ms 296 KB Guessed the password with 178 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 444 KB Guessed the password with 2750 queries.
2 Correct 58 ms 332 KB Guessed the password with 5070 queries.
3 Correct 70 ms 304 KB Guessed the password with 4588 queries.
4 Correct 96 ms 472 KB Guessed the password with 8084 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 58 queries.
2 Correct 1 ms 208 KB Guessed the password with 103 queries.
3 Correct 1 ms 256 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 1 ms 208 KB Guessed the password with 92 queries.
6 Correct 2 ms 296 KB Guessed the password with 178 queries.
7 Correct 22 ms 444 KB Guessed the password with 2750 queries.
8 Correct 58 ms 332 KB Guessed the password with 5070 queries.
9 Correct 70 ms 304 KB Guessed the password with 4588 queries.
10 Correct 96 ms 472 KB Guessed the password with 8084 queries.
11 Correct 82 ms 460 KB Guessed the password with 8154 queries.
12 Correct 114 ms 312 KB Guessed the password with 8162 queries.
13 Correct 103 ms 356 KB Guessed the password with 11502 queries.
14 Correct 90 ms 472 KB Guessed the password with 11602 queries.
15 Correct 152 ms 572 KB Guessed the password with 10880 queries.
16 Correct 126 ms 328 KB Guessed the password with 10861 queries.
17 Correct 86 ms 460 KB Guessed the password with 10211 queries.
18 Correct 142 ms 360 KB Guessed the password with 10247 queries.
19 Correct 133 ms 356 KB Guessed the password with 9688 queries.
20 Correct 138 ms 360 KB Guessed the password with 9775 queries.
21 Correct 164 ms 364 KB Guessed the password with 11639 queries.
22 Correct 158 ms 432 KB Guessed the password with 11710 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 58 queries.
2 Correct 1 ms 208 KB Guessed the password with 103 queries.
3 Correct 1 ms 256 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 1 ms 208 KB Guessed the password with 92 queries.
6 Correct 2 ms 296 KB Guessed the password with 178 queries.
7 Correct 22 ms 444 KB Guessed the password with 2750 queries.
8 Correct 58 ms 332 KB Guessed the password with 5070 queries.
9 Correct 70 ms 304 KB Guessed the password with 4588 queries.
10 Correct 96 ms 472 KB Guessed the password with 8084 queries.
11 Correct 82 ms 460 KB Guessed the password with 8154 queries.
12 Correct 114 ms 312 KB Guessed the password with 8162 queries.
13 Correct 103 ms 356 KB Guessed the password with 11502 queries.
14 Correct 90 ms 472 KB Guessed the password with 11602 queries.
15 Correct 152 ms 572 KB Guessed the password with 10880 queries.
16 Correct 126 ms 328 KB Guessed the password with 10861 queries.
17 Correct 86 ms 460 KB Guessed the password with 10211 queries.
18 Correct 142 ms 360 KB Guessed the password with 10247 queries.
19 Correct 133 ms 356 KB Guessed the password with 9688 queries.
20 Correct 138 ms 360 KB Guessed the password with 9775 queries.
21 Correct 164 ms 364 KB Guessed the password with 11639 queries.
22 Correct 158 ms 432 KB Guessed the password with 11710 queries.
23 Correct 264 ms 516 KB Guessed the password with 23704 queries.
24 Correct 281 ms 504 KB Guessed the password with 20965 queries.
25 Correct 341 ms 476 KB Guessed the password with 23669 queries.
26 Correct 249 ms 496 KB Guessed the password with 19100 queries.
27 Correct 267 ms 488 KB Guessed the password with 23703 queries.
28 Correct 274 ms 496 KB Guessed the password with 16821 queries.
29 Correct 328 ms 680 KB Guessed the password with 23707 queries.
30 Correct 229 ms 604 KB Guessed the password with 14391 queries.