oj.uz

Submission #851593

# Submission time Handle Problem Language Result Execution time Memory
851593 2023-09-20T07:55:44 Z MilosMilutinovic Password (RMI18_password) C++14
50 / 100
 288 ms 1212 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);
		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;
		int c=f[0];
		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;
	}
	return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 75 queries.
2 Correct 1 ms 344 KB Guessed the password with 185 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 496 KB Guessed the password with 117 queries.
3 Correct 1 ms 344 KB Guessed the password with 91 queries.
4 Correct 2 ms 364 KB Guessed the password with 215 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1212 KB Guessed the password with 4512 queries.
2 Correct 58 ms 788 KB Guessed the password with 10191 queries.
3 Correct 75 ms 956 KB Guessed the password with 12504 queries.
4 Correct 117 ms 728 KB Guessed the password with 20411 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 75 queries.
2 Correct 1 ms 344 KB Guessed the password with 185 queries.
3 Correct 0 ms 344 KB Guessed the password with 49 queries.
4 Correct 1 ms 496 KB Guessed the password with 117 queries.
5 Correct 1 ms 344 KB Guessed the password with 91 queries.
6 Correct 2 ms 364 KB Guessed the password with 215 queries.
7 Correct 22 ms 1212 KB Guessed the password with 4512 queries.
8 Correct 58 ms 788 KB Guessed the password with 10191 queries.
9 Correct 75 ms 956 KB Guessed the password with 12504 queries.
10 Correct 117 ms 728 KB Guessed the password with 20411 queries.
11 Correct 288 ms 988 KB Guessed the password with 49507 queries.
12 Correct 73 ms 1124 KB Guessed the password with 11387 queries.
13 Correct 271 ms 704 KB Guessed the password with 47681 queries.
14 Correct 129 ms 724 KB Guessed the password with 21355 queries.
15 Correct 268 ms 944 KB Guessed the password with 44836 queries.
16 Correct 108 ms 716 KB Guessed the password with 17935 queries.
17 Correct 277 ms 708 KB Guessed the password with 49794 queries.
18 Correct 79 ms 728 KB Guessed the password with 14831 queries.
19 Incorrect 257 ms 972 KB Could not guess the password with 50000 queries.
20 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 75 queries.
2 Correct 1 ms 344 KB Guessed the password with 185 queries.
3 Correct 0 ms 344 KB Guessed the password with 49 queries.
4 Correct 1 ms 496 KB Guessed the password with 117 queries.
5 Correct 1 ms 344 KB Guessed the password with 91 queries.
6 Correct 2 ms 364 KB Guessed the password with 215 queries.
7 Correct 22 ms 1212 KB Guessed the password with 4512 queries.
8 Correct 58 ms 788 KB Guessed the password with 10191 queries.
9 Correct 75 ms 956 KB Guessed the password with 12504 queries.
10 Correct 117 ms 728 KB Guessed the password with 20411 queries.
11 Correct 288 ms 988 KB Guessed the password with 49507 queries.
12 Correct 73 ms 1124 KB Guessed the password with 11387 queries.
13 Correct 271 ms 704 KB Guessed the password with 47681 queries.
14 Correct 129 ms 724 KB Guessed the password with 21355 queries.
15 Correct 268 ms 944 KB Guessed the password with 44836 queries.
16 Correct 108 ms 716 KB Guessed the password with 17935 queries.
17 Correct 277 ms 708 KB Guessed the password with 49794 queries.
18 Correct 79 ms 728 KB Guessed the password with 14831 queries.
19 Incorrect 257 ms 972 KB Could not guess the password with 50000 queries.
20 Halted 0 ms 0 KB -