oj.uz

Submission #851595

# Submission time Handle Problem Language Result Execution time Memory
851595 2023-09-20T07:57:44 Z MilosMilutinovic Password (RMI18_password) C++14
100 / 100
 260 ms 2168 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) {
	mt19937 rng(time(0));
	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;
		shuffle(f.begin(),f.end(),rng);
		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 76 queries.
2 Correct 1 ms 344 KB Guessed the password with 142 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Guessed the password with 48 queries.
2 Correct 1 ms 340 KB Guessed the password with 106 queries.
3 Correct 1 ms 596 KB Guessed the password with 92 queries.
4 Correct 2 ms 344 KB Guessed the password with 216 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 968 KB Guessed the password with 3873 queries.
2 Correct 34 ms 712 KB Guessed the password with 5194 queries.
3 Correct 39 ms 472 KB Guessed the password with 7481 queries.
4 Correct 67 ms 712 KB Guessed the password with 12161 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 76 queries.
2 Correct 1 ms 344 KB Guessed the password with 142 queries.
3 Correct 1 ms 340 KB Guessed the password with 48 queries.
4 Correct 1 ms 340 KB Guessed the password with 106 queries.
5 Correct 1 ms 596 KB Guessed the password with 92 queries.
6 Correct 2 ms 344 KB Guessed the password with 216 queries.
7 Correct 18 ms 968 KB Guessed the password with 3873 queries.
8 Correct 34 ms 712 KB Guessed the password with 5194 queries.
9 Correct 39 ms 472 KB Guessed the password with 7481 queries.
10 Correct 67 ms 712 KB Guessed the password with 12161 queries.
11 Correct 84 ms 960 KB Guessed the password with 13721 queries.
12 Correct 77 ms 732 KB Guessed the password with 13363 queries.
13 Correct 106 ms 980 KB Guessed the password with 18679 queries.
14 Correct 121 ms 712 KB Guessed the password with 19216 queries.
15 Correct 107 ms 988 KB Guessed the password with 18235 queries.
16 Correct 108 ms 724 KB Guessed the password with 18852 queries.
17 Correct 93 ms 940 KB Guessed the password with 15908 queries.
18 Correct 104 ms 704 KB Guessed the password with 16057 queries.
19 Correct 95 ms 988 KB Guessed the password with 15369 queries.
20 Correct 98 ms 980 KB Guessed the password with 15798 queries.
21 Correct 69 ms 980 KB Guessed the password with 12166 queries.
22 Correct 62 ms 968 KB Guessed the password with 11605 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 76 queries.
2 Correct 1 ms 344 KB Guessed the password with 142 queries.
3 Correct 1 ms 340 KB Guessed the password with 48 queries.
4 Correct 1 ms 340 KB Guessed the password with 106 queries.
5 Correct 1 ms 596 KB Guessed the password with 92 queries.
6 Correct 2 ms 344 KB Guessed the password with 216 queries.
7 Correct 18 ms 968 KB Guessed the password with 3873 queries.
8 Correct 34 ms 712 KB Guessed the password with 5194 queries.
9 Correct 39 ms 472 KB Guessed the password with 7481 queries.
10 Correct 67 ms 712 KB Guessed the password with 12161 queries.
11 Correct 84 ms 960 KB Guessed the password with 13721 queries.
12 Correct 77 ms 732 KB Guessed the password with 13363 queries.
13 Correct 106 ms 980 KB Guessed the password with 18679 queries.
14 Correct 121 ms 712 KB Guessed the password with 19216 queries.
15 Correct 107 ms 988 KB Guessed the password with 18235 queries.
16 Correct 108 ms 724 KB Guessed the password with 18852 queries.
17 Correct 93 ms 940 KB Guessed the password with 15908 queries.
18 Correct 104 ms 704 KB Guessed the password with 16057 queries.
19 Correct 95 ms 988 KB Guessed the password with 15369 queries.
20 Correct 98 ms 980 KB Guessed the password with 15798 queries.
21 Correct 69 ms 980 KB Guessed the password with 12166 queries.
22 Correct 62 ms 968 KB Guessed the password with 11605 queries.
23 Correct 153 ms 1656 KB Guessed the password with 25325 queries.
24 Correct 134 ms 1776 KB Guessed the password with 21527 queries.
25 Correct 260 ms 1640 KB Guessed the password with 37716 queries.
26 Correct 176 ms 1880 KB Guessed the password with 30039 queries.
27 Correct 230 ms 1320 KB Guessed the password with 40944 queries.
28 Correct 161 ms 1580 KB Guessed the password with 27677 queries.
29 Correct 248 ms 1876 KB Guessed the password with 43290 queries.
30 Correct 156 ms 2168 KB Guessed the password with 23973 queries.