oj.uz

Submission #660613

# Submission time Handle Problem Language Result Execution time Memory
660613 2022-11-22T15:44:16 Z angelo_torres Password (RMI18_password) C++17
80 / 100
 487 ms 580 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,12},{13,25},{26,26}};
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 328 queries.
2 Correct 5 ms 208 KB Guessed the password with 515 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 53 queries.
2 Correct 2 ms 208 KB Guessed the password with 147 queries.
3 Correct 3 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 113 ms 304 KB Guessed the password with 11133 queries.
2 Correct 164 ms 304 KB Guessed the password with 15443 queries.
3 Correct 179 ms 436 KB Guessed the password with 15488 queries.
4 Correct 194 ms 312 KB Guessed the password with 21590 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Guessed the password with 328 queries.
2 Correct 5 ms 208 KB Guessed the password with 515 queries.
3 Correct 2 ms 208 KB Guessed the password with 53 queries.
4 Correct 2 ms 208 KB Guessed the password with 147 queries.
5 Correct 3 ms 208 KB Guessed the password with 187 queries.
6 Correct 3 ms 208 KB Guessed the password with 313 queries.
7 Correct 113 ms 304 KB Guessed the password with 11133 queries.
8 Correct 164 ms 304 KB Guessed the password with 15443 queries.
9 Correct 179 ms 436 KB Guessed the password with 15488 queries.
10 Correct 194 ms 312 KB Guessed the password with 21590 queries.
11 Correct 353 ms 316 KB Guessed the password with 36683 queries.
12 Correct 337 ms 448 KB Guessed the password with 36708 queries.
13 Correct 393 ms 328 KB Guessed the password with 39310 queries.
14 Correct 376 ms 580 KB Guessed the password with 39304 queries.
15 Correct 440 ms 328 KB Guessed the password with 41906 queries.
16 Correct 345 ms 440 KB Guessed the password with 41911 queries.
17 Correct 395 ms 452 KB Guessed the password with 43202 queries.
18 Correct 371 ms 560 KB Guessed the password with 43212 queries.
19 Correct 412 ms 332 KB Guessed the password with 44511 queries.
20 Correct 448 ms 448 KB Guessed the password with 44511 queries.
21 Correct 460 ms 328 KB Guessed the password with 45778 queries.
22 Correct 426 ms 448 KB Guessed the password with 45811 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Guessed the password with 328 queries.
2 Correct 5 ms 208 KB Guessed the password with 515 queries.
3 Correct 2 ms 208 KB Guessed the password with 53 queries.
4 Correct 2 ms 208 KB Guessed the password with 147 queries.
5 Correct 3 ms 208 KB Guessed the password with 187 queries.
6 Correct 3 ms 208 KB Guessed the password with 313 queries.
7 Correct 113 ms 304 KB Guessed the password with 11133 queries.
8 Correct 164 ms 304 KB Guessed the password with 15443 queries.
9 Correct 179 ms 436 KB Guessed the password with 15488 queries.
10 Correct 194 ms 312 KB Guessed the password with 21590 queries.
11 Correct 353 ms 316 KB Guessed the password with 36683 queries.
12 Correct 337 ms 448 KB Guessed the password with 36708 queries.
13 Correct 393 ms 328 KB Guessed the password with 39310 queries.
14 Correct 376 ms 580 KB Guessed the password with 39304 queries.
15 Correct 440 ms 328 KB Guessed the password with 41906 queries.
16 Correct 345 ms 440 KB Guessed the password with 41911 queries.
17 Correct 395 ms 452 KB Guessed the password with 43202 queries.
18 Correct 371 ms 560 KB Guessed the password with 43212 queries.
19 Correct 412 ms 332 KB Guessed the password with 44511 queries.
20 Correct 448 ms 448 KB Guessed the password with 44511 queries.
21 Correct 460 ms 328 KB Guessed the password with 45778 queries.
22 Correct 426 ms 448 KB Guessed the password with 45811 queries.
23 Execution timed out 487 ms 556 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -