oj.uz

Submission #661023

# Submission time Handle Problem Language Result Execution time Memory
661023 2022-11-23T23:04:16 Z angelo_torres Password (RMI18_password) C++17
30 / 100
 164 ms 496 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,18},{19,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 208 KB Guessed the password with 109 queries.
2 Correct 2 ms 208 KB Guessed the password with 193 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 336 KB Guessed the password with 6010 queries.
2 Correct 98 ms 332 KB Guessed the password with 8391 queries.
3 Correct 126 ms 456 KB Guessed the password with 11215 queries.
4 Runtime error 164 ms 496 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
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 193 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 50 ms 336 KB Guessed the password with 6010 queries.
8 Correct 98 ms 332 KB Guessed the password with 8391 queries.
9 Correct 126 ms 456 KB Guessed the password with 11215 queries.
10 Runtime error 164 ms 496 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
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 193 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 50 ms 336 KB Guessed the password with 6010 queries.
8 Correct 98 ms 332 KB Guessed the password with 8391 queries.
9 Correct 126 ms 456 KB Guessed the password with 11215 queries.
10 Runtime error 164 ms 496 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -