oj.uz

Submission #394225

# Submission time Handle Problem Language Result Execution time Memory
394225 2021-04-26T07:43:20 Z jsannemo Password (RMI18_password) C++14
50 / 100
 1433 ms 20368 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 go(const string& pre, int N, int S) {
	if (S < 0) return "";


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

	string res;
	for (int i = cnt; i >= 0; --i) {
		string npre = pre;
		rep(j,0,i) npre.push_back('a' + S);

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

	return res;
}

string guess(int N, int S) {
	return go("", N, S - 1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 328 KB Guessed the password with 121 queries.
2 Correct 9 ms 200 KB Guessed the password with 277 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 29 queries.
2 Correct 2 ms 200 KB Guessed the password with 42 queries.
3 Correct 5 ms 200 KB Guessed the password with 162 queries.
4 Correct 5 ms 200 KB Guessed the password with 177 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 1228 KB Guessed the password with 7208 queries.
2 Correct 245 ms 984 KB Guessed the password with 8758 queries.
3 Correct 361 ms 1104 KB Guessed the password with 14453 queries.
4 Correct 506 ms 1920 KB Guessed the password with 19147 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 328 KB Guessed the password with 121 queries.
2 Correct 9 ms 200 KB Guessed the password with 277 queries.
3 Correct 2 ms 200 KB Guessed the password with 29 queries.
4 Correct 2 ms 200 KB Guessed the password with 42 queries.
5 Correct 5 ms 200 KB Guessed the password with 162 queries.
6 Correct 5 ms 200 KB Guessed the password with 177 queries.
7 Correct 188 ms 1228 KB Guessed the password with 7208 queries.
8 Correct 245 ms 984 KB Guessed the password with 8758 queries.
9 Correct 361 ms 1104 KB Guessed the password with 14453 queries.
10 Correct 506 ms 1920 KB Guessed the password with 19147 queries.
11 Correct 291 ms 1104 KB Guessed the password with 10068 queries.
12 Incorrect 1433 ms 20368 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 328 KB Guessed the password with 121 queries.
2 Correct 9 ms 200 KB Guessed the password with 277 queries.
3 Correct 2 ms 200 KB Guessed the password with 29 queries.
4 Correct 2 ms 200 KB Guessed the password with 42 queries.
5 Correct 5 ms 200 KB Guessed the password with 162 queries.
6 Correct 5 ms 200 KB Guessed the password with 177 queries.
7 Correct 188 ms 1228 KB Guessed the password with 7208 queries.
8 Correct 245 ms 984 KB Guessed the password with 8758 queries.
9 Correct 361 ms 1104 KB Guessed the password with 14453 queries.
10 Correct 506 ms 1920 KB Guessed the password with 19147 queries.
11 Correct 291 ms 1104 KB Guessed the password with 10068 queries.
12 Incorrect 1433 ms 20368 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -