oj.uz

답안 #394148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
394148 2021-04-25T21:22:25 Z jsannemo Password (RMI18_password) C++14
30 / 100
 412 ms 2368 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> rem(26);

string go(const string& pre, const string& post, int N, int S) {
	if (S < 0) return "";

	int hi = sz(pre) + sz(post) + rem[S] + 1;
	int lo = sz(pre) + sz(post);
	while (hi - lo > 1) {
		int mid = (lo + hi) / 2;
		cerr << "test tot length " << mid << " of char" << endl;

		string ask = pre;
		rep(i,0,mid - sz(pre) - sz(post)) ask.push_back('a' + S);
		ask.insert(ask.end(), post.begin(), post.end());
		int cnt = query(ask);
		if (cnt >= mid) lo = mid;
		else hi = mid;
	}

	int cnt = lo - sz(pre) - sz(post);
	cerr << "with pre " << pre << " and post " << post << " at " << (char)(S+'a') << " we found " << cnt << endl;

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

		string npost;
		rep(j,0,cnt-i) npost.push_back('a' + S);
		npost += post;

		res += go(npre, npost, N - sz(res) + i, S - 1);
		if (i != cnt) {
			res.push_back('a' + S);
			rem[S]--;
		}
	}

	return res;
}

string guess(int N, int S) {
	rep(i,0,S) {
		string s(N, 'a' + i);
		rem[i] = query(s);
	}
	return go("", "", N, S - 1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 204 KB Guessed the password with 115 queries.
2 Correct 4 ms 200 KB Guessed the password with 135 queries.
3 Correct 7 ms 328 KB Guessed the password with 328 queries.
4 Correct 13 ms 200 KB Guessed the password with 449 queries.

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 412 ms 2368 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 200 KB Guessed the password with 89 queries.
2 Correct 8 ms 200 KB Guessed the password with 158 queries.
3 Correct 3 ms 204 KB Guessed the password with 115 queries.
4 Correct 4 ms 200 KB Guessed the password with 135 queries.
5 Correct 7 ms 328 KB Guessed the password with 328 queries.
6 Correct 13 ms 200 KB Guessed the password with 449 queries.
7 Runtime error 412 ms 2368 KB Execution killed with signal 13
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 200 KB Guessed the password with 89 queries.
2 Correct 8 ms 200 KB Guessed the password with 158 queries.
3 Correct 3 ms 204 KB Guessed the password with 115 queries.
4 Correct 4 ms 200 KB Guessed the password with 135 queries.
5 Correct 7 ms 328 KB Guessed the password with 328 queries.
6 Correct 13 ms 200 KB Guessed the password with 449 queries.
7 Runtime error 412 ms 2368 KB Execution killed with signal 13
8 Halted 0 ms 0 KB -