oj.uz

Submission #709146

# Submission time Handle Problem Language Result Execution time Memory
709146 2023-03-13T06:52:14 Z zaneyu Password (RMI18_password) C++14
50 / 100
 539 ms 680 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;
	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 117 queries.
2 Correct 3 ms 208 KB Guessed the password with 291 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 126 queries.
3 Correct 1 ms 208 KB Guessed the password with 18 queries.
4 Correct 3 ms 208 KB Guessed the password with 266 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 336 KB Guessed the password with 7952 queries.
2 Correct 103 ms 528 KB Guessed the password with 11412 queries.
3 Correct 128 ms 556 KB Guessed the password with 17824 queries.
4 Correct 213 ms 488 KB Guessed the password with 25323 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 117 queries.
2 Correct 3 ms 208 KB Guessed the password with 291 queries.
3 Correct 1 ms 208 KB Guessed the password with 73 queries.
4 Correct 2 ms 208 KB Guessed the password with 126 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 3 ms 208 KB Guessed the password with 266 queries.
7 Correct 68 ms 336 KB Guessed the password with 7952 queries.
8 Correct 103 ms 528 KB Guessed the password with 11412 queries.
9 Correct 128 ms 556 KB Guessed the password with 17824 queries.
10 Correct 213 ms 488 KB Guessed the password with 25323 queries.
11 Incorrect 539 ms 680 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 117 queries.
2 Correct 3 ms 208 KB Guessed the password with 291 queries.
3 Correct 1 ms 208 KB Guessed the password with 73 queries.
4 Correct 2 ms 208 KB Guessed the password with 126 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 3 ms 208 KB Guessed the password with 266 queries.
7 Correct 68 ms 336 KB Guessed the password with 7952 queries.
8 Correct 103 ms 528 KB Guessed the password with 11412 queries.
9 Correct 128 ms 556 KB Guessed the password with 17824 queries.
10 Correct 213 ms 488 KB Guessed the password with 25323 queries.
11 Incorrect 539 ms 680 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -