oj.uz

Submission #851589

# Submission time Handle Problem Language Result Execution time Memory
851589 2023-09-20T07:52:15 Z MilosMilutinovic Password (RMI18_password) C++14
50 / 100
 297 ms 1456 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]]=false;
				}
				c=f[j];
			} else {
				ord[c][f[j]]=false;
			}
		}
		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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 121 queries.
2 Correct 1 ms 596 KB Guessed the password with 277 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Guessed the password with 49 queries.
2 Correct 1 ms 344 KB Guessed the password with 133 queries.
3 Correct 1 ms 344 KB Guessed the password with 169 queries.
4 Correct 1 ms 344 KB Guessed the password with 292 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 712 KB Guessed the password with 9609 queries.
2 Correct 81 ms 960 KB Guessed the password with 17345 queries.
3 Correct 106 ms 1456 KB Guessed the password with 21756 queries.
4 Correct 197 ms 728 KB Guessed the password with 36498 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 121 queries.
2 Correct 1 ms 596 KB Guessed the password with 277 queries.
3 Correct 0 ms 344 KB Guessed the password with 49 queries.
4 Correct 1 ms 344 KB Guessed the password with 133 queries.
5 Correct 1 ms 344 KB Guessed the password with 169 queries.
6 Correct 1 ms 344 KB Guessed the password with 292 queries.
7 Correct 56 ms 712 KB Guessed the password with 9609 queries.
8 Correct 81 ms 960 KB Guessed the password with 17345 queries.
9 Correct 106 ms 1456 KB Guessed the password with 21756 queries.
10 Correct 197 ms 728 KB Guessed the password with 36498 queries.
11 Incorrect 297 ms 712 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 1 ms 344 KB Guessed the password with 121 queries.
2 Correct 1 ms 596 KB Guessed the password with 277 queries.
3 Correct 0 ms 344 KB Guessed the password with 49 queries.
4 Correct 1 ms 344 KB Guessed the password with 133 queries.
5 Correct 1 ms 344 KB Guessed the password with 169 queries.
6 Correct 1 ms 344 KB Guessed the password with 292 queries.
7 Correct 56 ms 712 KB Guessed the password with 9609 queries.
8 Correct 81 ms 960 KB Guessed the password with 17345 queries.
9 Correct 106 ms 1456 KB Guessed the password with 21756 queries.
10 Correct 197 ms 728 KB Guessed the password with 36498 queries.
11 Incorrect 297 ms 712 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -