oj.uz

Submission #918471

# Submission time Handle Problem Language Result Execution time Memory
918471 2024-01-29T21:23:07 Z vjudge1 Password (RMI18_password) C++17
100 / 100
 327 ms 14360 KB 
#include <bits/stdc++.h>
using namespace std; 
int query(string str);
int N;
vector<int> a; 
int c[26][26][5001];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
bool comp(pair<int,int> x,pair<int,int> y){
	if(x.first==y.first){
		return x.second<y.second;
	}
	string s2="";
	for(int i=0;i<x.second;i++){
		s2+=char('a'+x.first); 
	}
	for(int i=0;i<a[y.first]-y.second+1;i++){
		s2+=char('a'+y.first);
	}
	for(int i=x.second;i<=N;i++){
		if(c[x.first][y.first][i]<=y.second){
			return true;
		}
	}
	for(int i=y.second;i<=N;i++){
		if(c[y.first][x.first][i]<=x.second){
			return false;
		}
	}
	bool ok=false; 
	if(query(s2)==(int)s2.size()){
		c[x.first][y.first][x.second]=min(c[x.first][y.first][x.second],y.second);
		ok=true;
	}
	else{
		c[y.first][x.first][y.second]=min(c[y.first][x.first][y.second],x.second);
	}
	return ok;
}
string guess(int n,int s){
	N=n;
	for(int i=0;i<s;i++){
		for(int j=0;j<s;j++){
			for(int z=1;z<=n;z++){
				c[i][j][z]=n+1;
			}
		}
	}
	a.resize(s);
	string s1=""; 
	for(int i=0;i<s;i++){
		s1=""; 
		for(int j=0;j<n;j++){
			s1+=char('a'+i); 
		}
		a[i]=query(s1); 
	}
	vector<pair<int,int>> b;
	for(int i=0;i<s;i++){
		for(int j=0;j<a[i];j++){
			b.push_back(make_pair(i,j+1));
		}
	}
	shuffle(b.begin(),b.end(),rng);
	sort(b.begin(),b.end(),comp); 
	s1="";
	for(int i=0;i<n;i++){
		s1+=char('a'+b[i].first);
	}
	return s1; 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 54 queries.
2 Correct 3 ms 12632 KB Guessed the password with 138 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Guessed the password with 49 queries.
2 Correct 1 ms 2508 KB Guessed the password with 116 queries.
3 Correct 1 ms 2504 KB Guessed the password with 19 queries.
4 Correct 2 ms 2508 KB Guessed the password with 245 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6672 KB Guessed the password with 3400 queries.
2 Correct 26 ms 8736 KB Guessed the password with 3950 queries.
3 Correct 55 ms 10796 KB Guessed the password with 6639 queries.
4 Correct 65 ms 10812 KB Guessed the password with 9227 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 54 queries.
2 Correct 3 ms 12632 KB Guessed the password with 138 queries.
3 Correct 1 ms 2392 KB Guessed the password with 49 queries.
4 Correct 1 ms 2508 KB Guessed the password with 116 queries.
5 Correct 1 ms 2504 KB Guessed the password with 19 queries.
6 Correct 2 ms 2508 KB Guessed the password with 245 queries.
7 Correct 27 ms 6672 KB Guessed the password with 3400 queries.
8 Correct 26 ms 8736 KB Guessed the password with 3950 queries.
9 Correct 55 ms 10796 KB Guessed the password with 6639 queries.
10 Correct 65 ms 10812 KB Guessed the password with 9227 queries.
11 Correct 107 ms 13492 KB Guessed the password with 11636 queries.
12 Correct 110 ms 13712 KB Guessed the password with 11726 queries.
13 Correct 111 ms 13544 KB Guessed the password with 13942 queries.
14 Correct 116 ms 13532 KB Guessed the password with 13761 queries.
15 Correct 128 ms 13572 KB Guessed the password with 14994 queries.
16 Correct 136 ms 13572 KB Guessed the password with 14947 queries.
17 Correct 131 ms 13800 KB Guessed the password with 13146 queries.
18 Correct 127 ms 13584 KB Guessed the password with 12982 queries.
19 Correct 136 ms 13604 KB Guessed the password with 13521 queries.
20 Correct 141 ms 13604 KB Guessed the password with 13937 queries.
21 Correct 92 ms 13844 KB Guessed the password with 8454 queries.
22 Correct 97 ms 13632 KB Guessed the password with 8041 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 54 queries.
2 Correct 3 ms 12632 KB Guessed the password with 138 queries.
3 Correct 1 ms 2392 KB Guessed the password with 49 queries.
4 Correct 1 ms 2508 KB Guessed the password with 116 queries.
5 Correct 1 ms 2504 KB Guessed the password with 19 queries.
6 Correct 2 ms 2508 KB Guessed the password with 245 queries.
7 Correct 27 ms 6672 KB Guessed the password with 3400 queries.
8 Correct 26 ms 8736 KB Guessed the password with 3950 queries.
9 Correct 55 ms 10796 KB Guessed the password with 6639 queries.
10 Correct 65 ms 10812 KB Guessed the password with 9227 queries.
11 Correct 107 ms 13492 KB Guessed the password with 11636 queries.
12 Correct 110 ms 13712 KB Guessed the password with 11726 queries.
13 Correct 111 ms 13544 KB Guessed the password with 13942 queries.
14 Correct 116 ms 13532 KB Guessed the password with 13761 queries.
15 Correct 128 ms 13572 KB Guessed the password with 14994 queries.
16 Correct 136 ms 13572 KB Guessed the password with 14947 queries.
17 Correct 131 ms 13800 KB Guessed the password with 13146 queries.
18 Correct 127 ms 13584 KB Guessed the password with 12982 queries.
19 Correct 136 ms 13604 KB Guessed the password with 13521 queries.
20 Correct 141 ms 13604 KB Guessed the password with 13937 queries.
21 Correct 92 ms 13844 KB Guessed the password with 8454 queries.
22 Correct 97 ms 13632 KB Guessed the password with 8041 queries.
23 Correct 180 ms 13880 KB Guessed the password with 16392 queries.
24 Correct 158 ms 14360 KB Guessed the password with 14226 queries.
25 Correct 280 ms 13876 KB Guessed the password with 27386 queries.
26 Correct 236 ms 13772 KB Guessed the password with 22369 queries.
27 Correct 312 ms 13776 KB Guessed the password with 31080 queries.
28 Correct 251 ms 13772 KB Guessed the password with 22316 queries.
29 Correct 327 ms 13768 KB Guessed the password with 32864 queries.
30 Correct 265 ms 14128 KB Guessed the password with 20668 queries.