oj.uz

답안 #394236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
394236 2021-04-26T08:06:11 Z jsannemo Password (RMI18_password) C++14
50 / 100
 589 ms 912 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 "";
	swap(alpha[S], alpha[rand() % (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 npre = pre + string(cnt, alpha[S]);
	vector<string> tres;
	for (int i = cnt; i >= 0; --i) {
		tres.push_back(go(npre, N, S - 1));
		npre.pop_back();
	}
	seen[alpha[S] - 'a'] += cnt;

	string res;
	for (int i = sz(tres) - 1; i >= 0; --i) {
		res.insert(res.end(), all(tres[i]));
		if (i) res.push_back(alpha[S]);
	}
	return res;
}

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 200 KB Guessed the password with 108 queries.
2 Correct 3 ms 200 KB Guessed the password with 236 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Guessed the password with 27 queries.
2 Correct 1 ms 200 KB Guessed the password with 40 queries.
3 Correct 2 ms 200 KB Guessed the password with 86 queries.
4 Correct 2 ms 200 KB Guessed the password with 141 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 440 KB Guessed the password with 6584 queries.
2 Correct 111 ms 332 KB Guessed the password with 10389 queries.
3 Correct 190 ms 352 KB Guessed the password with 14278 queries.
4 Correct 196 ms 376 KB Guessed the password with 18700 queries.

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 200 KB Guessed the password with 108 queries.
2 Correct 3 ms 200 KB Guessed the password with 236 queries.
3 Correct 1 ms 200 KB Guessed the password with 27 queries.
4 Correct 1 ms 200 KB Guessed the password with 40 queries.
5 Correct 2 ms 200 KB Guessed the password with 86 queries.
6 Correct 2 ms 200 KB Guessed the password with 141 queries.
7 Correct 67 ms 440 KB Guessed the password with 6584 queries.
8 Correct 111 ms 332 KB Guessed the password with 10389 queries.
9 Correct 190 ms 352 KB Guessed the password with 14278 queries.
10 Correct 196 ms 376 KB Guessed the password with 18700 queries.
11 Correct 336 ms 560 KB Guessed the password with 34810 queries.
12 Correct 450 ms 804 KB Guessed the password with 33285 queries.
13 Correct 456 ms 568 KB Guessed the password with 35543 queries.
14 Correct 366 ms 672 KB Guessed the password with 37940 queries.
15 Correct 459 ms 764 KB Guessed the password with 44827 queries.
16 Correct 400 ms 640 KB Guessed the password with 40173 queries.
17 Correct 427 ms 736 KB Guessed the password with 38668 queries.
18 Correct 547 ms 880 KB Guessed the password with 47768 queries.
19 Incorrect 589 ms 912 KB Could not guess the password with 50000 queries.
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 200 KB Guessed the password with 108 queries.
2 Correct 3 ms 200 KB Guessed the password with 236 queries.
3 Correct 1 ms 200 KB Guessed the password with 27 queries.
4 Correct 1 ms 200 KB Guessed the password with 40 queries.
5 Correct 2 ms 200 KB Guessed the password with 86 queries.
6 Correct 2 ms 200 KB Guessed the password with 141 queries.
7 Correct 67 ms 440 KB Guessed the password with 6584 queries.
8 Correct 111 ms 332 KB Guessed the password with 10389 queries.
9 Correct 190 ms 352 KB Guessed the password with 14278 queries.
10 Correct 196 ms 376 KB Guessed the password with 18700 queries.
11 Correct 336 ms 560 KB Guessed the password with 34810 queries.
12 Correct 450 ms 804 KB Guessed the password with 33285 queries.
13 Correct 456 ms 568 KB Guessed the password with 35543 queries.
14 Correct 366 ms 672 KB Guessed the password with 37940 queries.
15 Correct 459 ms 764 KB Guessed the password with 44827 queries.
16 Correct 400 ms 640 KB Guessed the password with 40173 queries.
17 Correct 427 ms 736 KB Guessed the password with 38668 queries.
18 Correct 547 ms 880 KB Guessed the password with 47768 queries.
19 Incorrect 589 ms 912 KB Could not guess the password with 50000 queries.
20 Halted 0 ms 0 KB -