oj.uz

답안 #660607

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660607 2022-11-22T15:27:17 Z angelo_torres Password (RMI18_password) C++17
50 / 100
 459 ms 428 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,19},{20,22},{23,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]
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 208 KB Guessed the password with 421 queries.
2 Correct 9 ms 308 KB Guessed the password with 795 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Guessed the password with 53 queries.
2 Correct 1 ms 208 KB Guessed the password with 147 queries.
3 Correct 2 ms 208 KB Guessed the password with 187 queries.
4 Correct 5 ms 208 KB Guessed the password with 313 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 428 KB Guessed the password with 11133 queries.
2 Correct 127 ms 308 KB Guessed the password with 18411 queries.
3 Correct 268 ms 304 KB Guessed the password with 27507 queries.
4 Correct 342 ms 316 KB Guessed the password with 38381 queries.

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 208 KB Guessed the password with 421 queries.
2 Correct 9 ms 308 KB Guessed the password with 795 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 1 ms 208 KB Guessed the password with 147 queries.
5 Correct 2 ms 208 KB Guessed the password with 187 queries.
6 Correct 5 ms 208 KB Guessed the password with 313 queries.
7 Correct 99 ms 428 KB Guessed the password with 11133 queries.
8 Correct 127 ms 308 KB Guessed the password with 18411 queries.
9 Correct 268 ms 304 KB Guessed the password with 27507 queries.
10 Correct 342 ms 316 KB Guessed the password with 38381 queries.
11 Incorrect 459 ms 320 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 208 KB Guessed the password with 421 queries.
2 Correct 9 ms 308 KB Guessed the password with 795 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 1 ms 208 KB Guessed the password with 147 queries.
5 Correct 2 ms 208 KB Guessed the password with 187 queries.
6 Correct 5 ms 208 KB Guessed the password with 313 queries.
7 Correct 99 ms 428 KB Guessed the password with 11133 queries.
8 Correct 127 ms 308 KB Guessed the password with 18411 queries.
9 Correct 268 ms 304 KB Guessed the password with 27507 queries.
10 Correct 342 ms 316 KB Guessed the password with 38381 queries.
11 Incorrect 459 ms 320 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -