oj.uz

Submission #851588

# Submission time Handle Problem Language Result Execution time Memory
851588 2023-09-20T07:50:50 Z MilosMilutinovic Password (RMI18_password) C++14
0 / 100
 5 ms 956 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> B;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

int cnt[30];
bool opn[30],ord[30][30];

int query(string s);

string guess(int n,int s) {
	rep(i,0,s) {
		cnt[i]=query(string(n,(char)('a'+i)));
	}
	string res="";
	rep(i,0,26) opn[i]=true;
	rep(i,0,26) rep(j,0,26) ord[i][j]=false;
	rep(i,0,n) {
		VI f;
		rep(j,0,26) if (cnt[j]>0) f.pb(j);
		int c=f[0];
		VI new_f;
		for (int x:f) {
			if (!opn[x]) {
				new_f.pb(x);
				continue;
			}
			bool ok=true;
			for (int y:f) {
				if (!opn[y]||x==y) {
					continue;
				}
				if (ord[y][x]) {
					ok=false;
				}
			}
			if (ok) {
				new_f.pb(x);
			}
		}
		f=new_f;
		for (int x:f) {
			opn[x]=true;
		}
		rep(j,1,SZ(f)) {
			string str=res;
			str+=(char)('a'+c);
			rep(k,0,cnt[f[j]]) str+=(char)('a'+f[j]);
			int qv=query(str);
			if (qv!=cnt[f[j]]+SZ(res)+1) {
				rep(q,0,j) {
					ord[f[j]][f[q]]=true;
				}
				c=f[j];
			} else {
				ord[c][f[j]]=true;
			}
		}
		rep(j,0,26) {
			ord[c][j]=ord[j][c]=false;
		}
		res+=(char)('a'+c);
		cnt[c]-=1;
		opn[c]=false;
	}
	return res;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Returned early from guess() after 42 queries.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 49 queries.
2 Correct 1 ms 344 KB Guessed the password with 117 queries.
3 Correct 1 ms 344 KB Guessed the password with 91 queries.
4 Incorrect 1 ms 588 KB Returned early from guess() after 72 queries.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 956 KB Returned early from guess() after 1011 queries.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Returned early from guess() after 42 queries.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Returned early from guess() after 42 queries.
2 Halted 0 ms 0 KB -