oj.uz

Submission #709153

# Submission time Handle Problem Language Result Execution time Memory
709153 2023-03-13T06:59:14 Z zaneyu Password (RMI18_password) C++17
80 / 100
 377 ms 940 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;
	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 123 queries.
2 Correct 3 ms 208 KB Guessed the password with 293 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 1 ms 208 KB Guessed the password with 124 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 45 ms 492 KB Guessed the password with 5227 queries.
2 Correct 53 ms 436 KB Guessed the password with 10782 queries.
3 Correct 114 ms 588 KB Guessed the password with 10401 queries.
4 Correct 168 ms 628 KB Guessed the password with 19069 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 123 queries.
2 Correct 3 ms 208 KB Guessed the password with 293 queries.
3 Correct 1 ms 208 KB Guessed the password with 57 queries.
4 Correct 1 ms 208 KB Guessed the password with 124 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 45 ms 492 KB Guessed the password with 5227 queries.
8 Correct 53 ms 436 KB Guessed the password with 10782 queries.
9 Correct 114 ms 588 KB Guessed the password with 10401 queries.
10 Correct 168 ms 628 KB Guessed the password with 19069 queries.
11 Correct 205 ms 492 KB Guessed the password with 19452 queries.
12 Correct 156 ms 548 KB Guessed the password with 20002 queries.
13 Correct 244 ms 688 KB Guessed the password with 27330 queries.
14 Correct 274 ms 896 KB Guessed the password with 27565 queries.
15 Correct 215 ms 656 KB Guessed the password with 26611 queries.
16 Correct 235 ms 616 KB Guessed the password with 26555 queries.
17 Correct 184 ms 732 KB Guessed the password with 23635 queries.
18 Correct 232 ms 780 KB Guessed the password with 23335 queries.
19 Correct 208 ms 700 KB Guessed the password with 23979 queries.
20 Correct 237 ms 584 KB Guessed the password with 24320 queries.
21 Correct 157 ms 584 KB Guessed the password with 19427 queries.
22 Correct 140 ms 724 KB Guessed the password with 19219 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 123 queries.
2 Correct 3 ms 208 KB Guessed the password with 293 queries.
3 Correct 1 ms 208 KB Guessed the password with 57 queries.
4 Correct 1 ms 208 KB Guessed the password with 124 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 45 ms 492 KB Guessed the password with 5227 queries.
8 Correct 53 ms 436 KB Guessed the password with 10782 queries.
9 Correct 114 ms 588 KB Guessed the password with 10401 queries.
10 Correct 168 ms 628 KB Guessed the password with 19069 queries.
11 Correct 205 ms 492 KB Guessed the password with 19452 queries.
12 Correct 156 ms 548 KB Guessed the password with 20002 queries.
13 Correct 244 ms 688 KB Guessed the password with 27330 queries.
14 Correct 274 ms 896 KB Guessed the password with 27565 queries.
15 Correct 215 ms 656 KB Guessed the password with 26611 queries.
16 Correct 235 ms 616 KB Guessed the password with 26555 queries.
17 Correct 184 ms 732 KB Guessed the password with 23635 queries.
18 Correct 232 ms 780 KB Guessed the password with 23335 queries.
19 Correct 208 ms 700 KB Guessed the password with 23979 queries.
20 Correct 237 ms 584 KB Guessed the password with 24320 queries.
21 Correct 157 ms 584 KB Guessed the password with 19427 queries.
22 Correct 140 ms 724 KB Guessed the password with 19219 queries.
23 Incorrect 377 ms 940 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -