oj.uz

Submission #660631

# Submission time Handle Problem Language Result Execution time Memory
660631 2022-11-22T17:20:40 Z angelo_torres Password (RMI18_password) C++17
80 / 100
 609 ms 736 KB 
#include <bits/stdc++.h>
#define sz(v) (int) v.size()
#define ff first
#define ss second

using namespace std;
typedef pair<int,int> ii;

int cn[26];
vector<int> a[26];
vector<ii> rn = {{0,8},{9,17},{18,25}};
deque<pair<int,char>> gr[3];
char ans[5005];

int query(string q);
// int query(string s){
// 	cout << s << endl;
// 	int tr; cin >> tr;
// 	return tr;
// }

string guess(int n,int s){
	// [0,7] 
	// [8,16]
	// [17,25]
	for(int i = 0; i < s; ++i) cn[i] = n;
	for(auto [l,r] : rn){
		for(int i = l; i <= r; ++i){
			for(int j = l; j <= r; ++j){
				if(i == j or i >= s or j >= s) continue;
				char x = (char) ('a'+i), y = (char) ('a'+j);
				string tr = "";
				for(int k = 1; k <= n; ++k) tr.push_back(y);
				for(int k = 1; k <= cn[i]; ++k){
					tr[k-1] = x;
					int vl = query(tr);
					if(vl < k) break;
					if(sz(a[i]) < k) a[i].push_back(vl-k);
					else a[i][k-1] += (vl-k);
				}
				cn[i] = sz(a[i]);
			}
		}
		// cout << endl;
	}
	for(int i = 0; i < 26; ++i) cn[i] = sz(a[i]);
	for(int i = 0; i < 26; ++i){
		for(int j = 0; j < sz(a[i]); ++j) a[i][j] += (sz(a[i])-j-1);
	}
	for(int i = 0; i < 3; ++i){
		int l = rn[i].ff, r = rn[i].ss;
		for(int j = l; j <= r; ++j){
			for(auto it : a[j]) gr[i].push_back({it,((char) ('a'+j))});
		}
		sort(gr[i].begin(), gr[i].end(), greater<pair<int,char>>());
		// for(auto it : gr[i]) cout << it.ff << " " << it.ss << " ";
		// cout << endl;
	} 
	for(int i = n; i >= 1; --i){
		vector<int> po;
		for(int j = 0; j < 3; ++j){
			if(sz(gr[j]) > 0 && gr[j].back().ff == n-i) po.push_back(j);
		}
		int rp = -1;
		if(sz(po) == 1) rp = po[0];
		if(sz(po) == 2){
			int i1 = po[0], i2 = po[1];
			string ft = "";
			for(auto it : gr[i1]) ft.push_back(it.ss);
			ft.push_back(gr[i2].back().ss);
			for(int j = i+1; j <= n; ++j) ft.push_back(ans[j]); 
			int vl = query(ft); 
			if(vl == sz(ft)) rp = i2;
			else rp = i1;
		}
		if(sz(po) == 3){
			int i1 = po[0], i2 = po[1], i3 = po[2];
			string ft = "";
			for(auto it : gr[i1]) ft.push_back(it.ss);
			ft.push_back(gr[i2].back().ss);
			for(int j = i+1; j <= n; ++j) ft.push_back(ans[j]);
			int vl = query(ft); 
			if(vl == sz(ft)) rp = i2;
			else rp = i1;

			ft = "";
			for(auto it : gr[rp]) ft.push_back(it.ss);
			ft.push_back(gr[i3].back().ss);
			for(int j = i+1; j <= n; ++j) ft.push_back(ans[j]);
			vl = query(ft); 
			if(vl == sz(ft)) rp = i3;
		}
		ans[i] = gr[rp].back().ss;
		gr[rp].pop_back();
		for(int j = 0; j < 3; ++j){
			if(j == rp) continue;
			for(auto &it : gr[j]) it.ff++;
		} 
	}
	string tt = "";
	for(int i = 1; i <= n; ++i) tt.push_back(ans[i]);
	return tt;
}

// int main(){
// 	int n,s; cin >> n >> s;
// 	cout << guess(n,s) << endl;
// 	return 0;
// }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 132 queries.
2 Correct 2 ms 208 KB Guessed the password with 231 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 53 queries.
2 Correct 2 ms 208 KB Guessed the password with 144 queries.
3 Correct 2 ms 208 KB Guessed the password with 184 queries.
4 Correct 3 ms 208 KB Guessed the password with 305 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 304 KB Guessed the password with 6671 queries.
2 Correct 99 ms 324 KB Guessed the password with 10275 queries.
3 Correct 111 ms 308 KB Guessed the password with 14418 queries.
4 Correct 142 ms 340 KB Guessed the password with 17779 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 132 queries.
2 Correct 2 ms 208 KB Guessed the password with 231 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 2 ms 208 KB Guessed the password with 144 queries.
5 Correct 2 ms 208 KB Guessed the password with 184 queries.
6 Correct 3 ms 208 KB Guessed the password with 305 queries.
7 Correct 68 ms 304 KB Guessed the password with 6671 queries.
8 Correct 99 ms 324 KB Guessed the password with 10275 queries.
9 Correct 111 ms 308 KB Guessed the password with 14418 queries.
10 Correct 142 ms 340 KB Guessed the password with 17779 queries.
11 Correct 250 ms 316 KB Guessed the password with 27706 queries.
12 Correct 241 ms 440 KB Guessed the password with 25688 queries.
13 Correct 381 ms 304 KB Guessed the password with 29546 queries.
14 Correct 264 ms 448 KB Guessed the password with 27941 queries.
15 Correct 316 ms 448 KB Guessed the password with 31394 queries.
16 Correct 333 ms 440 KB Guessed the password with 29632 queries.
17 Correct 455 ms 488 KB Guessed the password with 32955 queries.
18 Correct 278 ms 568 KB Guessed the password with 29918 queries.
19 Correct 377 ms 444 KB Guessed the password with 33961 queries.
20 Correct 339 ms 368 KB Guessed the password with 31151 queries.
21 Correct 460 ms 352 KB Guessed the password with 34864 queries.
22 Correct 288 ms 332 KB Guessed the password with 31865 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 132 queries.
2 Correct 2 ms 208 KB Guessed the password with 231 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 2 ms 208 KB Guessed the password with 144 queries.
5 Correct 2 ms 208 KB Guessed the password with 184 queries.
6 Correct 3 ms 208 KB Guessed the password with 305 queries.
7 Correct 68 ms 304 KB Guessed the password with 6671 queries.
8 Correct 99 ms 324 KB Guessed the password with 10275 queries.
9 Correct 111 ms 308 KB Guessed the password with 14418 queries.
10 Correct 142 ms 340 KB Guessed the password with 17779 queries.
11 Correct 250 ms 316 KB Guessed the password with 27706 queries.
12 Correct 241 ms 440 KB Guessed the password with 25688 queries.
13 Correct 381 ms 304 KB Guessed the password with 29546 queries.
14 Correct 264 ms 448 KB Guessed the password with 27941 queries.
15 Correct 316 ms 448 KB Guessed the password with 31394 queries.
16 Correct 333 ms 440 KB Guessed the password with 29632 queries.
17 Correct 455 ms 488 KB Guessed the password with 32955 queries.
18 Correct 278 ms 568 KB Guessed the password with 29918 queries.
19 Correct 377 ms 444 KB Guessed the password with 33961 queries.
20 Correct 339 ms 368 KB Guessed the password with 31151 queries.
21 Correct 460 ms 352 KB Guessed the password with 34864 queries.
22 Correct 288 ms 332 KB Guessed the password with 31865 queries.
23 Execution timed out 609 ms 736 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -