oj.uz

Submission #709115

# Submission time Handle Problem Language Result Execution time Memory
709115 2023-03-13T06:29:38 Z zaneyu Password (RMI18_password) C++14
50 / 100
 493 ms 724 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 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 a=1,b=N-sz(pf)-sz(sf);
	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);
	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 142 queries.
2 Correct 3 ms 208 KB Guessed the password with 307 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 71 queries.
2 Correct 2 ms 208 KB Guessed the password with 137 queries.
3 Correct 2 ms 208 KB Guessed the password with 97 queries.
4 Correct 3 ms 208 KB Guessed the password with 320 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 428 KB Guessed the password with 9882 queries.
2 Correct 144 ms 448 KB Guessed the password with 13242 queries.
3 Correct 225 ms 444 KB Guessed the password with 18680 queries.
4 Correct 335 ms 604 KB Guessed the password with 33107 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 142 queries.
2 Correct 3 ms 208 KB Guessed the password with 307 queries.
3 Correct 1 ms 208 KB Guessed the password with 71 queries.
4 Correct 2 ms 208 KB Guessed the password with 137 queries.
5 Correct 2 ms 208 KB Guessed the password with 97 queries.
6 Correct 3 ms 208 KB Guessed the password with 320 queries.
7 Correct 70 ms 428 KB Guessed the password with 9882 queries.
8 Correct 144 ms 448 KB Guessed the password with 13242 queries.
9 Correct 225 ms 444 KB Guessed the password with 18680 queries.
10 Correct 335 ms 604 KB Guessed the password with 33107 queries.
11 Correct 476 ms 724 KB Guessed the password with 43749 queries.
12 Incorrect 493 ms 676 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 2 ms 208 KB Guessed the password with 142 queries.
2 Correct 3 ms 208 KB Guessed the password with 307 queries.
3 Correct 1 ms 208 KB Guessed the password with 71 queries.
4 Correct 2 ms 208 KB Guessed the password with 137 queries.
5 Correct 2 ms 208 KB Guessed the password with 97 queries.
6 Correct 3 ms 208 KB Guessed the password with 320 queries.
7 Correct 70 ms 428 KB Guessed the password with 9882 queries.
8 Correct 144 ms 448 KB Guessed the password with 13242 queries.
9 Correct 225 ms 444 KB Guessed the password with 18680 queries.
10 Correct 335 ms 604 KB Guessed the password with 33107 queries.
11 Correct 476 ms 724 KB Guessed the password with 43749 queries.
12 Incorrect 493 ms 676 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -