oj.uz

Submission #394149

# Submission time Handle Problem Language Result Execution time Memory
394149 2021-04-25T21:33:11 Z jsannemo Password (RMI18_password) C++14
10 / 100
 593 ms 4516 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 cnt = 0;
	string mid(1, 'a' + S);
	if (query(pre + mid + post) == sz(pre) + 1 + sz(post)) {
		int hi = sz(pre) + sz(post) + rem[S] + 1;
		int lo = sz(pre) + sz(post) + 1;
		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;
		}
		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

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 74 queries.
2 Correct 3 ms 200 KB Guessed the password with 128 queries.
3 Runtime error 5 ms 300 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 1772 KB Guessed the password with 9832 queries.
2 Correct 350 ms 1588 KB Guessed the password with 11158 queries.
3 Correct 491 ms 1980 KB Guessed the password with 20503 queries.
4 Runtime error 593 ms 4516 KB Execution killed with signal 13

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 200 KB Guessed the password with 136 queries.
2 Correct 9 ms 200 KB Guessed the password with 300 queries.
3 Correct 2 ms 200 KB Guessed the password with 74 queries.
4 Correct 3 ms 200 KB Guessed the password with 128 queries.
5 Runtime error 5 ms 300 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 200 KB Guessed the password with 136 queries.
2 Correct 9 ms 200 KB Guessed the password with 300 queries.
3 Correct 2 ms 200 KB Guessed the password with 74 queries.
4 Correct 3 ms 200 KB Guessed the password with 128 queries.
5 Runtime error 5 ms 300 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -