oj.uz

Submission #394227

# Submission time Handle Problem Language Result Execution time Memory
394227 2021-04-26T07:56:13 Z jsannemo Password (RMI18_password) C++14
50 / 100
 1265 ms 6560 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int query(string q);

vector<int> seen(26);
string alpha;

string go(const string& pre, int N, int S) {
	if (S < 0) return "";
	random_shuffle(alpha.begin(), alpha.begin() + S + 1);


	string q = pre + string(N - sz(pre), alpha[S]);
	int cnt = query(q) - seen[alpha[S] - 'a'] - sz(pre);
	cerr << "pre " << pre << " S " << alpha[S] << " cnt " << cnt << endl;

	string res;
	for (int i = cnt; i >= 0; --i) {
		string npre = pre;
		rep(j,0,i) npre.push_back(alpha[S]);

		if (i != cnt) {
			res.insert(res.begin(), alpha[S]);
			seen[alpha[S] - 'a']++;
		}
		res = go(npre, N, S - 1) + res;
	}

	return res;
}

string guess(int N, int S) {
	rep(i,0,S) alpha.push_back('a' + i);
	return go("", N, S - 1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 200 KB Guessed the password with 131 queries.
2 Correct 8 ms 308 KB Guessed the password with 305 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Guessed the password with 29 queries.
2 Correct 1 ms 284 KB Guessed the password with 36 queries.
3 Correct 3 ms 300 KB Guessed the password with 86 queries.
4 Correct 4 ms 200 KB Guessed the password with 119 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 624 KB Guessed the password with 5426 queries.
2 Correct 216 ms 832 KB Guessed the password with 9456 queries.
3 Correct 370 ms 2052 KB Guessed the password with 14220 queries.
4 Correct 500 ms 1592 KB Guessed the password with 18343 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 200 KB Guessed the password with 131 queries.
2 Correct 8 ms 308 KB Guessed the password with 305 queries.
3 Correct 1 ms 296 KB Guessed the password with 29 queries.
4 Correct 1 ms 284 KB Guessed the password with 36 queries.
5 Correct 3 ms 300 KB Guessed the password with 86 queries.
6 Correct 4 ms 200 KB Guessed the password with 119 queries.
7 Correct 146 ms 624 KB Guessed the password with 5426 queries.
8 Correct 216 ms 832 KB Guessed the password with 9456 queries.
9 Correct 370 ms 2052 KB Guessed the password with 14220 queries.
10 Correct 500 ms 1592 KB Guessed the password with 18343 queries.
11 Correct 831 ms 2140 KB Guessed the password with 33659 queries.
12 Correct 786 ms 2420 KB Guessed the password with 32903 queries.
13 Correct 1146 ms 5212 KB Guessed the password with 38641 queries.
14 Correct 922 ms 4036 KB Guessed the password with 38302 queries.
15 Correct 1053 ms 6080 KB Guessed the password with 39050 queries.
16 Correct 1027 ms 5488 KB Guessed the password with 40569 queries.
17 Correct 1203 ms 3980 KB Guessed the password with 41515 queries.
18 Correct 1224 ms 6560 KB Guessed the password with 43358 queries.
19 Correct 1111 ms 3052 KB Guessed the password with 40755 queries.
20 Correct 1099 ms 3208 KB Guessed the password with 40516 queries.
21 Correct 1148 ms 3040 KB Guessed the password with 44587 queries.
22 Execution timed out 1265 ms 5808 KB Time limit exceeded (wall clock)

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 200 KB Guessed the password with 131 queries.
2 Correct 8 ms 308 KB Guessed the password with 305 queries.
3 Correct 1 ms 296 KB Guessed the password with 29 queries.
4 Correct 1 ms 284 KB Guessed the password with 36 queries.
5 Correct 3 ms 300 KB Guessed the password with 86 queries.
6 Correct 4 ms 200 KB Guessed the password with 119 queries.
7 Correct 146 ms 624 KB Guessed the password with 5426 queries.
8 Correct 216 ms 832 KB Guessed the password with 9456 queries.
9 Correct 370 ms 2052 KB Guessed the password with 14220 queries.
10 Correct 500 ms 1592 KB Guessed the password with 18343 queries.
11 Correct 831 ms 2140 KB Guessed the password with 33659 queries.
12 Correct 786 ms 2420 KB Guessed the password with 32903 queries.
13 Correct 1146 ms 5212 KB Guessed the password with 38641 queries.
14 Correct 922 ms 4036 KB Guessed the password with 38302 queries.
15 Correct 1053 ms 6080 KB Guessed the password with 39050 queries.
16 Correct 1027 ms 5488 KB Guessed the password with 40569 queries.
17 Correct 1203 ms 3980 KB Guessed the password with 41515 queries.
18 Correct 1224 ms 6560 KB Guessed the password with 43358 queries.
19 Correct 1111 ms 3052 KB Guessed the password with 40755 queries.
20 Correct 1099 ms 3208 KB Guessed the password with 40516 queries.
21 Correct 1148 ms 3040 KB Guessed the password with 44587 queries.
22 Execution timed out 1265 ms 5808 KB Time limit exceeded (wall clock)