oj.uz

답안 #709112

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709112 2023-03-13T06:28:59 Z zaneyu Password (RMI18_password) C++14
50 / 100
 483 ms 708 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;
}
string guess(int n, int s){
	REP(i,s) ord.pb(i);
	N=n,S=s;
	return rec("","",0);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 208 KB Guessed the password with 142 queries.
2 Correct 3 ms 208 KB Guessed the password with 313 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Guessed the password with 56 queries.
2 Correct 2 ms 208 KB Guessed the password with 155 queries.
3 Correct 1 ms 208 KB Guessed the password with 36 queries.
4 Correct 5 ms 296 KB Guessed the password with 327 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 312 KB Guessed the password with 7926 queries.
2 Correct 139 ms 428 KB Guessed the password with 13657 queries.
3 Correct 215 ms 540 KB Guessed the password with 21254 queries.
4 Correct 273 ms 536 KB Guessed the password with 30631 queries.

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 208 KB Guessed the password with 142 queries.
2 Correct 3 ms 208 KB Guessed the password with 313 queries.
3 Correct 1 ms 208 KB Guessed the password with 56 queries.
4 Correct 2 ms 208 KB Guessed the password with 155 queries.
5 Correct 1 ms 208 KB Guessed the password with 36 queries.
6 Correct 5 ms 296 KB Guessed the password with 327 queries.
7 Correct 87 ms 312 KB Guessed the password with 7926 queries.
8 Correct 139 ms 428 KB Guessed the password with 13657 queries.
9 Correct 215 ms 540 KB Guessed the password with 21254 queries.
10 Correct 273 ms 536 KB Guessed the password with 30631 queries.
11 Incorrect 483 ms 708 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 208 KB Guessed the password with 142 queries.
2 Correct 3 ms 208 KB Guessed the password with 313 queries.
3 Correct 1 ms 208 KB Guessed the password with 56 queries.
4 Correct 2 ms 208 KB Guessed the password with 155 queries.
5 Correct 1 ms 208 KB Guessed the password with 36 queries.
6 Correct 5 ms 296 KB Guessed the password with 327 queries.
7 Correct 87 ms 312 KB Guessed the password with 7926 queries.
8 Correct 139 ms 428 KB Guessed the password with 13657 queries.
9 Correct 215 ms 540 KB Guessed the password with 21254 queries.
10 Correct 273 ms 536 KB Guessed the password with 30631 queries.
11 Incorrect 483 ms 708 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -