oj.uz

Submission #851549

# Submission time Handle Problem Language Result Execution time Memory
851549 2023-09-20T06:14:52 Z MilosMilutinovic Password (RMI18_password) C++14
50 / 100
 254 ms 1204 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];

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,n) {
		VI f;
		rep(j,0,26) if (cnt[j]>0) f.pb(j);
		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) {
				c=f[j];
			}
		}
		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 121 queries.
2 Correct 1 ms 344 KB Guessed the password with 277 queries.

Subtask #2
20.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 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 50 ms 708 KB Guessed the password with 9609 queries.
2 Correct 85 ms 944 KB Guessed the password with 17345 queries.
3 Correct 119 ms 1204 KB Guessed the password with 21756 queries.
4 Correct 206 ms 700 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 344 KB Guessed the password with 277 queries.
3 Correct 1 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 50 ms 708 KB Guessed the password with 9609 queries.
8 Correct 85 ms 944 KB Guessed the password with 17345 queries.
9 Correct 119 ms 1204 KB Guessed the password with 21756 queries.
10 Correct 206 ms 700 KB Guessed the password with 36498 queries.
11 Incorrect 254 ms 700 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 344 KB Guessed the password with 277 queries.
3 Correct 1 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 50 ms 708 KB Guessed the password with 9609 queries.
8 Correct 85 ms 944 KB Guessed the password with 17345 queries.
9 Correct 119 ms 1204 KB Guessed the password with 21756 queries.
10 Correct 206 ms 700 KB Guessed the password with 36498 queries.
11 Incorrect 254 ms 700 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -