oj.uz

Submission #918467

# Submission time Handle Problem Language Result Execution time Memory
918467 2024-01-29T21:19:43 Z Huseyn123 Password (RMI18_password) C++17
80 / 100
 468 ms 14168 KB 
#include <bits/stdc++.h>
using namespace std; 
int query(string str);
int N;
vector<int> a; 
int c[26][26][5001];
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));
		}
	}
	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 83 queries.
2 Correct 2 ms 12632 KB Guessed the password with 120 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Guessed the password with 70 queries.
2 Correct 1 ms 2508 KB Guessed the password with 123 queries.
3 Correct 1 ms 2500 KB Guessed the password with 10 queries.
4 Correct 2 ms 2512 KB Guessed the password with 319 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6488 KB Guessed the password with 5585 queries.
2 Correct 40 ms 8896 KB Guessed the password with 6480 queries.
3 Correct 60 ms 10792 KB Guessed the password with 9720 queries.
4 Correct 92 ms 10824 KB Guessed the password with 13648 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 83 queries.
2 Correct 2 ms 12632 KB Guessed the password with 120 queries.
3 Correct 1 ms 2392 KB Guessed the password with 70 queries.
4 Correct 1 ms 2508 KB Guessed the password with 123 queries.
5 Correct 1 ms 2500 KB Guessed the password with 10 queries.
6 Correct 2 ms 2512 KB Guessed the password with 319 queries.
7 Correct 32 ms 6488 KB Guessed the password with 5585 queries.
8 Correct 40 ms 8896 KB Guessed the password with 6480 queries.
9 Correct 60 ms 10792 KB Guessed the password with 9720 queries.
10 Correct 92 ms 10824 KB Guessed the password with 13648 queries.
11 Correct 150 ms 13492 KB Guessed the password with 18946 queries.
12 Correct 151 ms 13708 KB Guessed the password with 19192 queries.
13 Correct 184 ms 13536 KB Guessed the password with 22595 queries.
14 Correct 164 ms 13540 KB Guessed the password with 20418 queries.
15 Correct 184 ms 13580 KB Guessed the password with 23369 queries.
16 Correct 174 ms 13576 KB Guessed the password with 22849 queries.
17 Correct 175 ms 13596 KB Guessed the password with 20938 queries.
18 Correct 174 ms 13652 KB Guessed the password with 21033 queries.
19 Correct 186 ms 13608 KB Guessed the password with 22206 queries.
20 Correct 221 ms 13608 KB Guessed the password with 23722 queries.
21 Correct 166 ms 13636 KB Guessed the password with 19488 queries.
22 Correct 133 ms 13632 KB Guessed the password with 15341 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Guessed the password with 83 queries.
2 Correct 2 ms 12632 KB Guessed the password with 120 queries.
3 Correct 1 ms 2392 KB Guessed the password with 70 queries.
4 Correct 1 ms 2508 KB Guessed the password with 123 queries.
5 Correct 1 ms 2500 KB Guessed the password with 10 queries.
6 Correct 2 ms 2512 KB Guessed the password with 319 queries.
7 Correct 32 ms 6488 KB Guessed the password with 5585 queries.
8 Correct 40 ms 8896 KB Guessed the password with 6480 queries.
9 Correct 60 ms 10792 KB Guessed the password with 9720 queries.
10 Correct 92 ms 10824 KB Guessed the password with 13648 queries.
11 Correct 150 ms 13492 KB Guessed the password with 18946 queries.
12 Correct 151 ms 13708 KB Guessed the password with 19192 queries.
13 Correct 184 ms 13536 KB Guessed the password with 22595 queries.
14 Correct 164 ms 13540 KB Guessed the password with 20418 queries.
15 Correct 184 ms 13580 KB Guessed the password with 23369 queries.
16 Correct 174 ms 13576 KB Guessed the password with 22849 queries.
17 Correct 175 ms 13596 KB Guessed the password with 20938 queries.
18 Correct 174 ms 13652 KB Guessed the password with 21033 queries.
19 Correct 186 ms 13608 KB Guessed the password with 22206 queries.
20 Correct 221 ms 13608 KB Guessed the password with 23722 queries.
21 Correct 166 ms 13636 KB Guessed the password with 19488 queries.
22 Correct 133 ms 13632 KB Guessed the password with 15341 queries.
23 Correct 310 ms 13844 KB Guessed the password with 30549 queries.
24 Correct 257 ms 13764 KB Guessed the password with 26533 queries.
25 Correct 432 ms 13860 KB Guessed the password with 43889 queries.
26 Correct 328 ms 13864 KB Guessed the password with 36101 queries.
27 Correct 468 ms 14168 KB Guessed the password with 48218 queries.
28 Correct 344 ms 13932 KB Guessed the password with 34339 queries.
29 Incorrect 456 ms 13684 KB Could not guess the password with 50000 queries.
30 Halted 0 ms 0 KB -