oj.uz

Submission #709135

# Submission time Handle Problem Language Result Execution time Memory
709135 2023-03-13T06:37:22 Z zaneyu Password (RMI18_password) C++14
50 / 100
 441 ms 668 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 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(69);
string guess(int n, int s){
	REP(i,s) ord.pb(i);
	shuffle(ALL(ord),rng);
	REP(i,s){
		string z="";
		REP(a,n) z.pb(ord[i]+'a');
		cnt[i]=query(z);
	}
	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 137 queries.
2 Correct 3 ms 208 KB Guessed the password with 286 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 73 queries.
2 Correct 2 ms 208 KB Guessed the password with 125 queries.
3 Correct 1 ms 208 KB Guessed the password with 96 queries.
4 Correct 2 ms 208 KB Guessed the password with 276 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 572 KB Guessed the password with 8630 queries.
2 Correct 84 ms 664 KB Guessed the password with 11304 queries.
3 Correct 150 ms 576 KB Guessed the password with 15932 queries.
4 Correct 236 ms 560 KB Guessed the password with 28161 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 137 queries.
2 Correct 3 ms 208 KB Guessed the password with 286 queries.
3 Correct 1 ms 208 KB Guessed the password with 73 queries.
4 Correct 2 ms 208 KB Guessed the password with 125 queries.
5 Correct 1 ms 208 KB Guessed the password with 96 queries.
6 Correct 2 ms 208 KB Guessed the password with 276 queries.
7 Correct 76 ms 572 KB Guessed the password with 8630 queries.
8 Correct 84 ms 664 KB Guessed the password with 11304 queries.
9 Correct 150 ms 576 KB Guessed the password with 15932 queries.
10 Correct 236 ms 560 KB Guessed the password with 28161 queries.
11 Correct 441 ms 616 KB Guessed the password with 38928 queries.
12 Incorrect 437 ms 668 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 137 queries.
2 Correct 3 ms 208 KB Guessed the password with 286 queries.
3 Correct 1 ms 208 KB Guessed the password with 73 queries.
4 Correct 2 ms 208 KB Guessed the password with 125 queries.
5 Correct 1 ms 208 KB Guessed the password with 96 queries.
6 Correct 2 ms 208 KB Guessed the password with 276 queries.
7 Correct 76 ms 572 KB Guessed the password with 8630 queries.
8 Correct 84 ms 664 KB Guessed the password with 11304 queries.
9 Correct 150 ms 576 KB Guessed the password with 15932 queries.
10 Correct 236 ms 560 KB Guessed the password with 28161 queries.
11 Correct 441 ms 616 KB Guessed the password with 38928 queries.
12 Incorrect 437 ms 668 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -