oj.uz

Submission #660614

# Submission time Handle Problem Language Result Execution time Memory
660614 2022-11-22T15:55:58 Z angelo_torres Password (RMI18_password) C++17
80 / 100
 623 ms 600 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(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 <= n; ++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);
				}
			}
		}
	}
	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 3 ms 208 KB Guessed the password with 219 queries.
2 Correct 4 ms 208 KB Guessed the password with 372 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Guessed the password with 53 queries.
2 Correct 1 ms 208 KB Guessed the password with 147 queries.
3 Correct 2 ms 208 KB Guessed the password with 187 queries.
4 Correct 3 ms 208 KB Guessed the password with 313 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 304 KB Guessed the password with 6737 queries.
2 Correct 103 ms 320 KB Guessed the password with 10362 queries.
3 Correct 147 ms 304 KB Guessed the password with 14544 queries.
4 Correct 160 ms 324 KB Guessed the password with 17905 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Guessed the password with 219 queries.
2 Correct 4 ms 208 KB Guessed the password with 372 queries.
3 Correct 1 ms 308 KB Guessed the password with 53 queries.
4 Correct 1 ms 208 KB Guessed the password with 147 queries.
5 Correct 2 ms 208 KB Guessed the password with 187 queries.
6 Correct 3 ms 208 KB Guessed the password with 313 queries.
7 Correct 65 ms 304 KB Guessed the password with 6737 queries.
8 Correct 103 ms 320 KB Guessed the password with 10362 queries.
9 Correct 147 ms 304 KB Guessed the password with 14544 queries.
10 Correct 160 ms 324 KB Guessed the password with 17905 queries.
11 Correct 347 ms 316 KB Guessed the password with 27880 queries.
12 Correct 214 ms 600 KB Guessed the password with 25862 queries.
13 Correct 353 ms 596 KB Guessed the password with 29720 queries.
14 Correct 244 ms 324 KB Guessed the password with 28115 queries.
15 Correct 407 ms 432 KB Guessed the password with 31568 queries.
16 Correct 371 ms 448 KB Guessed the password with 29806 queries.
17 Correct 403 ms 452 KB Guessed the password with 33129 queries.
18 Correct 251 ms 448 KB Guessed the password with 30092 queries.
19 Correct 344 ms 332 KB Guessed the password with 34135 queries.
20 Correct 324 ms 364 KB Guessed the password with 31325 queries.
21 Correct 468 ms 360 KB Guessed the password with 35038 queries.
22 Correct 255 ms 332 KB Guessed the password with 32039 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Guessed the password with 219 queries.
2 Correct 4 ms 208 KB Guessed the password with 372 queries.
3 Correct 1 ms 308 KB Guessed the password with 53 queries.
4 Correct 1 ms 208 KB Guessed the password with 147 queries.
5 Correct 2 ms 208 KB Guessed the password with 187 queries.
6 Correct 3 ms 208 KB Guessed the password with 313 queries.
7 Correct 65 ms 304 KB Guessed the password with 6737 queries.
8 Correct 103 ms 320 KB Guessed the password with 10362 queries.
9 Correct 147 ms 304 KB Guessed the password with 14544 queries.
10 Correct 160 ms 324 KB Guessed the password with 17905 queries.
11 Correct 347 ms 316 KB Guessed the password with 27880 queries.
12 Correct 214 ms 600 KB Guessed the password with 25862 queries.
13 Correct 353 ms 596 KB Guessed the password with 29720 queries.
14 Correct 244 ms 324 KB Guessed the password with 28115 queries.
15 Correct 407 ms 432 KB Guessed the password with 31568 queries.
16 Correct 371 ms 448 KB Guessed the password with 29806 queries.
17 Correct 403 ms 452 KB Guessed the password with 33129 queries.
18 Correct 251 ms 448 KB Guessed the password with 30092 queries.
19 Correct 344 ms 332 KB Guessed the password with 34135 queries.
20 Correct 324 ms 364 KB Guessed the password with 31325 queries.
21 Correct 468 ms 360 KB Guessed the password with 35038 queries.
22 Correct 255 ms 332 KB Guessed the password with 32039 queries.
23 Execution timed out 623 ms 504 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -