oj.uz

Submission #661024

# Submission time Handle Problem Language Result Execution time Memory
661024 2022-11-23T23:11:20 Z angelo_torres Password (RMI18_password) C++17
80 / 100
 692 ms 740 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<ii> rn = {{0,5},{6,11},{12,17},{18,25}};
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]
	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 < 4; ++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){
		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 388 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 3 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 46 ms 340 KB Guessed the password with 6010 queries.
2 Correct 94 ms 348 KB Guessed the password with 8391 queries.
3 Correct 76 ms 320 KB Guessed the password with 11215 queries.
4 Correct 161 ms 324 KB Guessed the password with 14735 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 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 3 ms 208 KB Guessed the password with 184 queries.
6 Correct 3 ms 208 KB Guessed the password with 305 queries.
7 Correct 46 ms 340 KB Guessed the password with 6010 queries.
8 Correct 94 ms 348 KB Guessed the password with 8391 queries.
9 Correct 76 ms 320 KB Guessed the password with 11215 queries.
10 Correct 161 ms 324 KB Guessed the password with 14735 queries.
11 Correct 318 ms 452 KB Guessed the password with 22204 queries.
12 Correct 298 ms 452 KB Guessed the password with 26935 queries.
13 Correct 300 ms 480 KB Guessed the password with 24946 queries.
14 Correct 327 ms 584 KB Guessed the password with 28130 queries.
15 Correct 347 ms 508 KB Guessed the password with 26816 queries.
16 Correct 270 ms 464 KB Guessed the password with 30325 queries.
17 Correct 354 ms 720 KB Guessed the password with 26076 queries.
18 Correct 217 ms 452 KB Guessed the password with 29543 queries.
19 Correct 427 ms 632 KB Guessed the password with 27186 queries.
20 Correct 364 ms 712 KB Guessed the password with 32932 queries.
21 Correct 353 ms 460 KB Guessed the password with 28246 queries.
22 Correct 338 ms 584 KB Guessed the password with 34285 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 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 3 ms 208 KB Guessed the password with 184 queries.
6 Correct 3 ms 208 KB Guessed the password with 305 queries.
7 Correct 46 ms 340 KB Guessed the password with 6010 queries.
8 Correct 94 ms 348 KB Guessed the password with 8391 queries.
9 Correct 76 ms 320 KB Guessed the password with 11215 queries.
10 Correct 161 ms 324 KB Guessed the password with 14735 queries.
11 Correct 318 ms 452 KB Guessed the password with 22204 queries.
12 Correct 298 ms 452 KB Guessed the password with 26935 queries.
13 Correct 300 ms 480 KB Guessed the password with 24946 queries.
14 Correct 327 ms 584 KB Guessed the password with 28130 queries.
15 Correct 347 ms 508 KB Guessed the password with 26816 queries.
16 Correct 270 ms 464 KB Guessed the password with 30325 queries.
17 Correct 354 ms 720 KB Guessed the password with 26076 queries.
18 Correct 217 ms 452 KB Guessed the password with 29543 queries.
19 Correct 427 ms 632 KB Guessed the password with 27186 queries.
20 Correct 364 ms 712 KB Guessed the password with 32932 queries.
21 Correct 353 ms 460 KB Guessed the password with 28246 queries.
22 Correct 338 ms 584 KB Guessed the password with 34285 queries.
23 Correct 652 ms 624 KB Guessed the password with 43031 queries.
24 Correct 616 ms 740 KB Guessed the password with 44360 queries.
25 Correct 610 ms 600 KB Guessed the password with 43148 queries.
26 Correct 669 ms 612 KB Guessed the password with 41291 queries.
27 Execution timed out 692 ms 576 KB Time limit exceeded (wall clock)
28 Halted 0 ms 0 KB -