oj.uz

Submission #709131

# Submission time Handle Problem Language Result Execution time Memory
709131 2023-03-13T06:36:31 Z zaneyu Password (RMI18_password) C++14
50 / 100
 537 ms 636 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(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 157 queries.
2 Correct 7 ms 256 KB Guessed the password with 337 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 208 KB Guessed the password with 149 queries.
3 Correct 1 ms 208 KB Guessed the password with 100 queries.
4 Correct 5 ms 208 KB Guessed the password with 346 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 544 KB Guessed the password with 9994 queries.
2 Correct 144 ms 456 KB Guessed the password with 13549 queries.
3 Correct 181 ms 472 KB Guessed the password with 19104 queries.
4 Correct 349 ms 636 KB Guessed the password with 33298 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 157 queries.
2 Correct 7 ms 256 KB Guessed the password with 337 queries.
3 Correct 1 ms 208 KB Guessed the password with 76 queries.
4 Correct 2 ms 208 KB Guessed the password with 149 queries.
5 Correct 1 ms 208 KB Guessed the password with 100 queries.
6 Correct 5 ms 208 KB Guessed the password with 346 queries.
7 Correct 95 ms 544 KB Guessed the password with 9994 queries.
8 Correct 144 ms 456 KB Guessed the password with 13549 queries.
9 Correct 181 ms 472 KB Guessed the password with 19104 queries.
10 Correct 349 ms 636 KB Guessed the password with 33298 queries.
11 Correct 450 ms 544 KB Guessed the password with 44483 queries.
12 Incorrect 537 ms 460 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 157 queries.
2 Correct 7 ms 256 KB Guessed the password with 337 queries.
3 Correct 1 ms 208 KB Guessed the password with 76 queries.
4 Correct 2 ms 208 KB Guessed the password with 149 queries.
5 Correct 1 ms 208 KB Guessed the password with 100 queries.
6 Correct 5 ms 208 KB Guessed the password with 346 queries.
7 Correct 95 ms 544 KB Guessed the password with 9994 queries.
8 Correct 144 ms 456 KB Guessed the password with 13549 queries.
9 Correct 181 ms 472 KB Guessed the password with 19104 queries.
10 Correct 349 ms 636 KB Guessed the password with 33298 queries.
11 Correct 450 ms 544 KB Guessed the password with 44483 queries.
12 Incorrect 537 ms 460 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -