oj.uz

Submission #709152

# Submission time Handle Problem Language Result Execution time Memory
709152 2023-03-13T06:57:42 Z zaneyu Password (RMI18_password) C++14
80 / 100
 323 ms 788 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 cnt2[26],cnt[26];
int query(string str);
int N,S;
vector<int> ord;
string rec(string pf,string sf,int cur){
	//cout<<pf<<' '<<sf<<' '<<cur<<'\n';
	bool hv=0;
	for(int i=cur;i<S;i++){
		string z=pf;
		z.pb(ord[i]+'a');
		z+=sf;
		if(sz(z)<=N and query(z)==sz(z)){
			hv=1;
			cur=i;
			break;
		}
	}
	if(!hv){
		//cout<<"NO\n";
		return "";
	}
	int mx=cnt[cur];
	for(auto x:pf) if(x-'a'==ord[cur]) --mx; 
	for(auto x:sf) if(x-'a'==ord[cur]) --mx; 
	int a=1,b=mx+1;
	while(a<b){
		int m=(a+b+1)/2;
		string z=pf;
		REP(j,m) z.pb(ord[cur]+'a');
		z+=sf;
		if(sz(z)<=N and query(z)==sz(z)) a=m;
		else b=m-1;
	}
	string ans="";
	REP(x,a+1){
		string z;
		REP(y,a-x) z.pb(ord[cur]+'a');
		z+=sf;
		string tmp=rec(pf+ans,z,cur+1);
		ans+=tmp;
		ans.pb(ord[cur]+'a');
	}
	ans.pop_back();
	//cout<<pf<<' '<<sf<<' '<<cur;
	//cout<<"RETURNED: "<<ans<<'\n';
	return ans;
}
mt19937 rng(429);
bool cmp(int a,int b){
	return cnt2[a]<cnt2[b];
} 
string guess(int n, int s){
	REP(i,s){
		string z="";
		REP(a,n) z.pb(i+'a');
		cnt2[i]=query(z);
	}
	REP(i,s) ord.pb(i);
	sort(ALL(ord),cmp);
	REP(i,s) cnt[i]=cnt2[ord[i]];
	N=n,S=s;
	return rec("","",0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 137 queries.
2 Correct 4 ms 220 KB Guessed the password with 315 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Guessed the password with 60 queries.
2 Correct 2 ms 208 KB Guessed the password with 125 queries.
3 Correct 1 ms 208 KB Guessed the password with 18 queries.
4 Correct 2 ms 208 KB Guessed the password with 254 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 476 KB Guessed the password with 5254 queries.
2 Correct 114 ms 432 KB Guessed the password with 10826 queries.
3 Correct 89 ms 564 KB Guessed the password with 10459 queries.
4 Correct 208 ms 560 KB Guessed the password with 19149 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 137 queries.
2 Correct 4 ms 220 KB Guessed the password with 315 queries.
3 Correct 1 ms 336 KB Guessed the password with 60 queries.
4 Correct 2 ms 208 KB Guessed the password with 125 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 2 ms 208 KB Guessed the password with 254 queries.
7 Correct 51 ms 476 KB Guessed the password with 5254 queries.
8 Correct 114 ms 432 KB Guessed the password with 10826 queries.
9 Correct 89 ms 564 KB Guessed the password with 10459 queries.
10 Correct 208 ms 560 KB Guessed the password with 19149 queries.
11 Correct 172 ms 620 KB Guessed the password with 19504 queries.
12 Correct 171 ms 592 KB Guessed the password with 20068 queries.
13 Correct 232 ms 684 KB Guessed the password with 27423 queries.
14 Correct 176 ms 616 KB Guessed the password with 27645 queries.
15 Correct 231 ms 788 KB Guessed the password with 26674 queries.
16 Correct 271 ms 604 KB Guessed the password with 26642 queries.
17 Correct 145 ms 572 KB Guessed the password with 23706 queries.
18 Correct 186 ms 616 KB Guessed the password with 23396 queries.
19 Correct 186 ms 748 KB Guessed the password with 24040 queries.
20 Correct 235 ms 724 KB Guessed the password with 24386 queries.
21 Correct 184 ms 616 KB Guessed the password with 19480 queries.
22 Correct 129 ms 692 KB Guessed the password with 19272 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 137 queries.
2 Correct 4 ms 220 KB Guessed the password with 315 queries.
3 Correct 1 ms 336 KB Guessed the password with 60 queries.
4 Correct 2 ms 208 KB Guessed the password with 125 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 2 ms 208 KB Guessed the password with 254 queries.
7 Correct 51 ms 476 KB Guessed the password with 5254 queries.
8 Correct 114 ms 432 KB Guessed the password with 10826 queries.
9 Correct 89 ms 564 KB Guessed the password with 10459 queries.
10 Correct 208 ms 560 KB Guessed the password with 19149 queries.
11 Correct 172 ms 620 KB Guessed the password with 19504 queries.
12 Correct 171 ms 592 KB Guessed the password with 20068 queries.
13 Correct 232 ms 684 KB Guessed the password with 27423 queries.
14 Correct 176 ms 616 KB Guessed the password with 27645 queries.
15 Correct 231 ms 788 KB Guessed the password with 26674 queries.
16 Correct 271 ms 604 KB Guessed the password with 26642 queries.
17 Correct 145 ms 572 KB Guessed the password with 23706 queries.
18 Correct 186 ms 616 KB Guessed the password with 23396 queries.
19 Correct 186 ms 748 KB Guessed the password with 24040 queries.
20 Correct 235 ms 724 KB Guessed the password with 24386 queries.
21 Correct 184 ms 616 KB Guessed the password with 19480 queries.
22 Correct 129 ms 692 KB Guessed the password with 19272 queries.
23 Incorrect 323 ms 736 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -