oj.uz

Submission #394150

# Submission time Handle Problem Language Result Execution time Memory
394150 2021-04-25T21:34:53 Z jsannemo Password (RMI18_password) C++14
50 / 100
 1682 ms 41504 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 (rem[S] && 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 3 ms 200 KB Guessed the password with 89 queries.
2 Correct 7 ms 200 KB Guessed the password with 158 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 74 queries.
2 Correct 4 ms 296 KB Guessed the password with 128 queries.
3 Correct 6 ms 292 KB Guessed the password with 174 queries.
4 Correct 8 ms 312 KB Guessed the password with 293 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 1888 KB Guessed the password with 8664 queries.
2 Correct 287 ms 1416 KB Guessed the password with 10757 queries.
3 Correct 503 ms 1768 KB Guessed the password with 16864 queries.
4 Correct 630 ms 4556 KB Guessed the password with 24334 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 89 queries.
2 Correct 7 ms 200 KB Guessed the password with 158 queries.
3 Correct 2 ms 200 KB Guessed the password with 74 queries.
4 Correct 4 ms 296 KB Guessed the password with 128 queries.
5 Correct 6 ms 292 KB Guessed the password with 174 queries.
6 Correct 8 ms 312 KB Guessed the password with 293 queries.
7 Correct 227 ms 1888 KB Guessed the password with 8664 queries.
8 Correct 287 ms 1416 KB Guessed the password with 10757 queries.
9 Correct 503 ms 1768 KB Guessed the password with 16864 queries.
10 Correct 630 ms 4556 KB Guessed the password with 24334 queries.
11 Correct 530 ms 1968 KB Guessed the password with 21643 queries.
12 Runtime error 1682 ms 41504 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 89 queries.
2 Correct 7 ms 200 KB Guessed the password with 158 queries.
3 Correct 2 ms 200 KB Guessed the password with 74 queries.
4 Correct 4 ms 296 KB Guessed the password with 128 queries.
5 Correct 6 ms 292 KB Guessed the password with 174 queries.
6 Correct 8 ms 312 KB Guessed the password with 293 queries.
7 Correct 227 ms 1888 KB Guessed the password with 8664 queries.
8 Correct 287 ms 1416 KB Guessed the password with 10757 queries.
9 Correct 503 ms 1768 KB Guessed the password with 16864 queries.
10 Correct 630 ms 4556 KB Guessed the password with 24334 queries.
11 Correct 530 ms 1968 KB Guessed the password with 21643 queries.
12 Runtime error 1682 ms 41504 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -