oj.uz

Submission #661030

# Submission time Handle Problem Language Result Execution time Memory
661030 2022-11-23T23:42:26 Z angelo_torres Password (RMI18_password) C++17
100 / 100
 700 ms 820 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];
// 6 6 7 7
vector<vector<int>> rn(4);
deque<pair<int,char>> gr[4];
char ans[5005];
 
int query(string q);
// int query(string s){
// 	cout << s << endl;
// 	int tr; cin >> tr;
// 	return tr;
// }
vector<int> po;

int com(int i1,int i2,int id,int nn){
	if(i1 == -1) return i2;
	if(i2 == -1) return i1;
	string tr = "";
	for(auto it : gr[i1]) tr.push_back(it.ss);
	tr.push_back(gr[i2].back().ss);
	for(int i = id+1; i <= nn; ++i) tr.push_back(ans[i]);
	if(query(tr) == sz(tr)) return i2;
	return i1;
}

string guess(int n,int s){
	// [0,7] 
	// [8,16]
	// [17,25]
	rn[0] = {0,1,2,3,4,5,25};
	rn[1] = {6,7,8,9,10,11};
	rn[2] = {12,13,14,15,16,17};
	rn[3] = {18,19,20,21,22,23,24};
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int i = 0; i < s; ++i) cn[i] = n;
	for(int id = 0; id < 4; ++id){
		vector<int> it = rn[id];
		for(int i : it){
			for(int j : it){
				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 id = 0; id < 4; ++id){
		vector<int> vi = rn[id];
		for(int j : vi){
			for(auto it : a[j]) gr[id].push_back({it,((char) ('a'+j))});
		}
		sort(gr[id].begin(), gr[id].end(), greater<pair<int,char>>());
		// for(auto it : gr[id]) cout << it.ff << " " << it.ss << " ";
		// cout << endl;
	} 
	for(int i = n; i >= 1; --i){
		for(int j = 0; j < 4; ++j){
			if(sz(gr[j]) > 0 && gr[j].back().ff == n-i) po.push_back(j);
		}
		int rp = -1;
		for(int j = 0; j < sz(po); ++j) rp = com(rp,po[j],i,n);
		ans[i] = gr[rp].back().ss;
		gr[rp].pop_back();
		for(int j = 0; j < 4; ++j){
			if(j == rp) continue;
			for(auto &it : gr[j]) it.ff++;
		} 
		po.clear();
	}
	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 109 queries.
2 Correct 2 ms 208 KB Guessed the password with 189 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 1 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 42 ms 444 KB Guessed the password with 6010 queries.
2 Correct 57 ms 452 KB Guessed the password with 8391 queries.
3 Correct 137 ms 336 KB Guessed the password with 11215 queries.
4 Correct 191 ms 368 KB Guessed the password with 14735 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 109 queries.
2 Correct 2 ms 208 KB Guessed the password with 189 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 1 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 42 ms 444 KB Guessed the password with 6010 queries.
8 Correct 57 ms 452 KB Guessed the password with 8391 queries.
9 Correct 137 ms 336 KB Guessed the password with 11215 queries.
10 Correct 191 ms 368 KB Guessed the password with 14735 queries.
11 Correct 329 ms 480 KB Guessed the password with 24558 queries.
12 Correct 208 ms 388 KB Guessed the password with 24734 queries.
13 Correct 378 ms 464 KB Guessed the password with 26308 queries.
14 Correct 293 ms 632 KB Guessed the password with 26370 queries.
15 Correct 370 ms 592 KB Guessed the password with 28356 queries.
16 Correct 302 ms 452 KB Guessed the password with 28135 queries.
17 Correct 436 ms 508 KB Guessed the password with 28912 queries.
18 Correct 262 ms 584 KB Guessed the password with 27318 queries.
19 Correct 379 ms 576 KB Guessed the password with 30072 queries.
20 Correct 333 ms 592 KB Guessed the password with 30277 queries.
21 Correct 402 ms 596 KB Guessed the password with 30861 queries.
22 Correct 321 ms 492 KB Guessed the password with 31275 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 109 queries.
2 Correct 2 ms 208 KB Guessed the password with 189 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 1 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 42 ms 444 KB Guessed the password with 6010 queries.
8 Correct 57 ms 452 KB Guessed the password with 8391 queries.
9 Correct 137 ms 336 KB Guessed the password with 11215 queries.
10 Correct 191 ms 368 KB Guessed the password with 14735 queries.
11 Correct 329 ms 480 KB Guessed the password with 24558 queries.
12 Correct 208 ms 388 KB Guessed the password with 24734 queries.
13 Correct 378 ms 464 KB Guessed the password with 26308 queries.
14 Correct 293 ms 632 KB Guessed the password with 26370 queries.
15 Correct 370 ms 592 KB Guessed the password with 28356 queries.
16 Correct 302 ms 452 KB Guessed the password with 28135 queries.
17 Correct 436 ms 508 KB Guessed the password with 28912 queries.
18 Correct 262 ms 584 KB Guessed the password with 27318 queries.
19 Correct 379 ms 576 KB Guessed the password with 30072 queries.
20 Correct 333 ms 592 KB Guessed the password with 30277 queries.
21 Correct 402 ms 596 KB Guessed the password with 30861 queries.
22 Correct 321 ms 492 KB Guessed the password with 31275 queries.
23 Correct 700 ms 620 KB Guessed the password with 42696 queries.
24 Correct 640 ms 528 KB Guessed the password with 43081 queries.
25 Correct 564 ms 584 KB Guessed the password with 42758 queries.
26 Correct 681 ms 820 KB Guessed the password with 42822 queries.
27 Correct 680 ms 524 KB Guessed the password with 42725 queries.
28 Correct 536 ms 568 KB Guessed the password with 42346 queries.
29 Correct 674 ms 676 KB Guessed the password with 42658 queries.
30 Correct 687 ms 576 KB Guessed the password with 41818 queries.