oj.uz

Submission #709142

# Submission time Handle Problem Language Result Execution time Memory
709142 2023-03-13T06:45:24 Z zaneyu Password (RMI18_password) C++14
50 / 100
 386 ms 568 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=N;
	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);
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 2 ms 208 KB Guessed the password with 151 queries.
2 Correct 5 ms 208 KB Guessed the password with 364 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 76 queries.
2 Correct 2 ms 304 KB Guessed the password with 152 queries.
3 Correct 1 ms 208 KB Guessed the password with 25 queries.
4 Correct 4 ms 300 KB Guessed the password with 341 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 396 KB Guessed the password with 9408 queries.
2 Correct 123 ms 408 KB Guessed the password with 13655 queries.
3 Correct 219 ms 484 KB Guessed the password with 21084 queries.
4 Correct 326 ms 504 KB Guessed the password with 30607 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 151 queries.
2 Correct 5 ms 208 KB Guessed the password with 364 queries.
3 Correct 1 ms 208 KB Guessed the password with 76 queries.
4 Correct 2 ms 304 KB Guessed the password with 152 queries.
5 Correct 1 ms 208 KB Guessed the password with 25 queries.
6 Correct 4 ms 300 KB Guessed the password with 341 queries.
7 Correct 73 ms 396 KB Guessed the password with 9408 queries.
8 Correct 123 ms 408 KB Guessed the password with 13655 queries.
9 Correct 219 ms 484 KB Guessed the password with 21084 queries.
10 Correct 326 ms 504 KB Guessed the password with 30607 queries.
11 Incorrect 386 ms 568 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 151 queries.
2 Correct 5 ms 208 KB Guessed the password with 364 queries.
3 Correct 1 ms 208 KB Guessed the password with 76 queries.
4 Correct 2 ms 304 KB Guessed the password with 152 queries.
5 Correct 1 ms 208 KB Guessed the password with 25 queries.
6 Correct 4 ms 300 KB Guessed the password with 341 queries.
7 Correct 73 ms 396 KB Guessed the password with 9408 queries.
8 Correct 123 ms 408 KB Guessed the password with 13655 queries.
9 Correct 219 ms 484 KB Guessed the password with 21084 queries.
10 Correct 326 ms 504 KB Guessed the password with 30607 queries.
11 Incorrect 386 ms 568 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -