oj.uz

Submission #709161

# Submission time Handle Problem Language Result Execution time Memory
709161 2023-03-13T07:05:48 Z zaneyu Password (RMI18_password) C++14
80 / 100
 497 ms 872 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++){
		int mx=cnt[i];
		for(auto x:pf) if(x-'a'==ord[i]) --mx; 
		for(auto x:sf) if(x-'a'==ord[i]) --mx; 
		if(mx==0) continue;
		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;
	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 1 ms 208 KB Guessed the password with 77 queries.
2 Correct 2 ms 208 KB Guessed the password with 170 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 57 queries.
2 Correct 2 ms 208 KB Guessed the password with 122 queries.
3 Correct 1 ms 208 KB Guessed the password with 18 queries.
4 Correct 3 ms 208 KB Guessed the password with 249 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 484 KB Guessed the password with 5213 queries.
2 Correct 101 ms 496 KB Guessed the password with 10274 queries.
3 Correct 94 ms 472 KB Guessed the password with 10388 queries.
4 Correct 170 ms 624 KB Guessed the password with 18912 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 77 queries.
2 Correct 2 ms 208 KB Guessed the password with 170 queries.
3 Correct 1 ms 208 KB Guessed the password with 57 queries.
4 Correct 2 ms 208 KB Guessed the password with 122 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 3 ms 208 KB Guessed the password with 249 queries.
7 Correct 52 ms 484 KB Guessed the password with 5213 queries.
8 Correct 101 ms 496 KB Guessed the password with 10274 queries.
9 Correct 94 ms 472 KB Guessed the password with 10388 queries.
10 Correct 170 ms 624 KB Guessed the password with 18912 queries.
11 Correct 188 ms 500 KB Guessed the password with 19366 queries.
12 Correct 214 ms 628 KB Guessed the password with 19944 queries.
13 Correct 252 ms 568 KB Guessed the password with 27182 queries.
14 Correct 233 ms 740 KB Guessed the password with 27407 queries.
15 Correct 202 ms 688 KB Guessed the password with 26557 queries.
16 Correct 306 ms 644 KB Guessed the password with 26487 queries.
17 Correct 219 ms 644 KB Guessed the password with 23564 queries.
18 Correct 243 ms 536 KB Guessed the password with 23200 queries.
19 Correct 196 ms 872 KB Guessed the password with 23911 queries.
20 Correct 229 ms 752 KB Guessed the password with 24254 queries.
21 Correct 226 ms 636 KB Guessed the password with 19201 queries.
22 Correct 188 ms 504 KB Guessed the password with 18817 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 77 queries.
2 Correct 2 ms 208 KB Guessed the password with 170 queries.
3 Correct 1 ms 208 KB Guessed the password with 57 queries.
4 Correct 2 ms 208 KB Guessed the password with 122 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 3 ms 208 KB Guessed the password with 249 queries.
7 Correct 52 ms 484 KB Guessed the password with 5213 queries.
8 Correct 101 ms 496 KB Guessed the password with 10274 queries.
9 Correct 94 ms 472 KB Guessed the password with 10388 queries.
10 Correct 170 ms 624 KB Guessed the password with 18912 queries.
11 Correct 188 ms 500 KB Guessed the password with 19366 queries.
12 Correct 214 ms 628 KB Guessed the password with 19944 queries.
13 Correct 252 ms 568 KB Guessed the password with 27182 queries.
14 Correct 233 ms 740 KB Guessed the password with 27407 queries.
15 Correct 202 ms 688 KB Guessed the password with 26557 queries.
16 Correct 306 ms 644 KB Guessed the password with 26487 queries.
17 Correct 219 ms 644 KB Guessed the password with 23564 queries.
18 Correct 243 ms 536 KB Guessed the password with 23200 queries.
19 Correct 196 ms 872 KB Guessed the password with 23911 queries.
20 Correct 229 ms 752 KB Guessed the password with 24254 queries.
21 Correct 226 ms 636 KB Guessed the password with 19201 queries.
22 Correct 188 ms 504 KB Guessed the password with 18817 queries.
23 Incorrect 497 ms 532 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -