oj.uz

Submission #660639

# Submission time Handle Problem Language Result Execution time Memory
660639 2022-11-22T17:27:22 Z angelo_torres Password (RMI18_password) C++17
80 / 100
 582 ms 616 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]
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	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 2 ms 208 KB Guessed the password with 132 queries.
2 Correct 3 ms 336 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 40 ms 340 KB Guessed the password with 6671 queries.
2 Correct 89 ms 324 KB Guessed the password with 10275 queries.
3 Correct 161 ms 328 KB Guessed the password with 14418 queries.
4 Correct 136 ms 336 KB Guessed the password with 17779 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 132 queries.
2 Correct 3 ms 336 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 40 ms 340 KB Guessed the password with 6671 queries.
8 Correct 89 ms 324 KB Guessed the password with 10275 queries.
9 Correct 161 ms 328 KB Guessed the password with 14418 queries.
10 Correct 136 ms 336 KB Guessed the password with 17779 queries.
11 Correct 213 ms 340 KB Guessed the password with 27706 queries.
12 Correct 164 ms 340 KB Guessed the password with 25688 queries.
13 Correct 335 ms 464 KB Guessed the password with 29546 queries.
14 Correct 306 ms 460 KB Guessed the password with 27941 queries.
15 Correct 394 ms 596 KB Guessed the password with 31394 queries.
16 Correct 290 ms 336 KB Guessed the password with 29632 queries.
17 Correct 348 ms 468 KB Guessed the password with 32955 queries.
18 Correct 392 ms 472 KB Guessed the password with 29918 queries.
19 Correct 388 ms 588 KB Guessed the password with 33961 queries.
20 Correct 265 ms 588 KB Guessed the password with 31151 queries.
21 Correct 385 ms 348 KB Guessed the password with 34864 queries.
22 Correct 428 ms 344 KB Guessed the password with 31865 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 132 queries.
2 Correct 3 ms 336 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 40 ms 340 KB Guessed the password with 6671 queries.
8 Correct 89 ms 324 KB Guessed the password with 10275 queries.
9 Correct 161 ms 328 KB Guessed the password with 14418 queries.
10 Correct 136 ms 336 KB Guessed the password with 17779 queries.
11 Correct 213 ms 340 KB Guessed the password with 27706 queries.
12 Correct 164 ms 340 KB Guessed the password with 25688 queries.
13 Correct 335 ms 464 KB Guessed the password with 29546 queries.
14 Correct 306 ms 460 KB Guessed the password with 27941 queries.
15 Correct 394 ms 596 KB Guessed the password with 31394 queries.
16 Correct 290 ms 336 KB Guessed the password with 29632 queries.
17 Correct 348 ms 468 KB Guessed the password with 32955 queries.
18 Correct 392 ms 472 KB Guessed the password with 29918 queries.
19 Correct 388 ms 588 KB Guessed the password with 33961 queries.
20 Correct 265 ms 588 KB Guessed the password with 31151 queries.
21 Correct 385 ms 348 KB Guessed the password with 34864 queries.
22 Correct 428 ms 344 KB Guessed the password with 31865 queries.
23 Execution timed out 582 ms 616 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -