oj.uz

Submission #244224

# Submission time Handle Problem Language Result Execution time Memory
244224 2020-07-03T01:28:16 Z MohamedAhmed04 Password (RMI18_password) C++14
100 / 100
 356 ms 768 KB 
#include <bits/stdc++.h>
 
using namespace std ;
 
const int MAX = 1e5 + 10 ;
 
int arr[MAX] , freq[27] , before[27][27] , letters[MAX] ;
int n , c ;
 
string ans = "" ;
 
int query(string s);
 
bool Check_Before(int a , int b)
{
	string s = ans ;
	s.push_back((char)(a+'a')) ;
	for(int i = 0 ; i < freq[b] ; ++i)
		s.push_back((char)(b+'a')) ;
	return (query(s) == s.size()) ;
}
 
bool cmp(int &a , int &b)
{
	return before[a][b] ;
}
 
string guess(int n , int c)
{
	for(int i = 0 ; i < c ; ++i)
		freq[i] = query(string(n , (char)('a'+i))) ;
	for(int i = 0 ; i < c ; ++i)
	{
		for(int j = i+1 ; j < c ; ++j)
		{
			before[i][j] = Check_Before(i , j) ;
			if(!before[i][j])
				before[j][i] = 1 ;
		}
	}
	for(int i = 0 ; i < c ; ++i)
		letters[i] = i ;
	sort(letters , letters + c , cmp) ;
	for(int i = 0 ; i < n ; ++i)
	{
		int x = letters[0] ;
		freq[x]-- ;
		ans.push_back((char)(x+'a')) ;
		int l = 1 , r = c-1 ;
		int idx = 0 ;
		if(freq[x] == 0)
			idx = c-1 ;
		else
		{
			while(l <= r)
			{
				int mid = (l + r) >> 1 ;
				if(!Check_Before(letters[0] , letters[mid]))
					idx = mid , l = mid+1 ;
				else
					r = mid-1 ;
			}
		}
		for(int i = 0 ; i < idx ; ++i)
			letters[i] = letters[i+1] ;
		letters[idx] = x ;
	}
	return ans ;
}

Compilation message

password.cpp: In function 'bool Check_Before(int, int)':
password.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return (query(s) == s.size()) ;
          ~~~~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Guessed the password with 121 queries.
2 Correct 7 ms 384 KB Guessed the password with 277 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 51 queries.
2 Correct 6 ms 384 KB Guessed the password with 104 queries.
3 Correct 5 ms 384 KB Guessed the password with 92 queries.
4 Correct 7 ms 384 KB Guessed the password with 202 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 480 KB Guessed the password with 3584 queries.
2 Correct 51 ms 384 KB Guessed the password with 4635 queries.
3 Correct 91 ms 384 KB Guessed the password with 6597 queries.
4 Correct 90 ms 384 KB Guessed the password with 8655 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Guessed the password with 121 queries.
2 Correct 7 ms 384 KB Guessed the password with 277 queries.
3 Correct 5 ms 384 KB Guessed the password with 51 queries.
4 Correct 6 ms 384 KB Guessed the password with 104 queries.
5 Correct 5 ms 384 KB Guessed the password with 92 queries.
6 Correct 7 ms 384 KB Guessed the password with 202 queries.
7 Correct 55 ms 480 KB Guessed the password with 3584 queries.
8 Correct 51 ms 384 KB Guessed the password with 4635 queries.
9 Correct 91 ms 384 KB Guessed the password with 6597 queries.
10 Correct 90 ms 384 KB Guessed the password with 8655 queries.
11 Correct 149 ms 480 KB Guessed the password with 13158 queries.
12 Correct 188 ms 504 KB Guessed the password with 13177 queries.
13 Correct 172 ms 512 KB Guessed the password with 14135 queries.
14 Correct 179 ms 420 KB Guessed the password with 14141 queries.
15 Correct 197 ms 480 KB Guessed the password with 15122 queries.
16 Correct 176 ms 480 KB Guessed the password with 15189 queries.
17 Correct 157 ms 508 KB Guessed the password with 15441 queries.
18 Correct 215 ms 632 KB Guessed the password with 15401 queries.
19 Correct 210 ms 632 KB Guessed the password with 15913 queries.
20 Correct 231 ms 504 KB Guessed the password with 15982 queries.
21 Correct 198 ms 392 KB Guessed the password with 15531 queries.
22 Correct 225 ms 384 KB Guessed the password with 15498 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Guessed the password with 121 queries.
2 Correct 7 ms 384 KB Guessed the password with 277 queries.
3 Correct 5 ms 384 KB Guessed the password with 51 queries.
4 Correct 6 ms 384 KB Guessed the password with 104 queries.
5 Correct 5 ms 384 KB Guessed the password with 92 queries.
6 Correct 7 ms 384 KB Guessed the password with 202 queries.
7 Correct 55 ms 480 KB Guessed the password with 3584 queries.
8 Correct 51 ms 384 KB Guessed the password with 4635 queries.
9 Correct 91 ms 384 KB Guessed the password with 6597 queries.
10 Correct 90 ms 384 KB Guessed the password with 8655 queries.
11 Correct 149 ms 480 KB Guessed the password with 13158 queries.
12 Correct 188 ms 504 KB Guessed the password with 13177 queries.
13 Correct 172 ms 512 KB Guessed the password with 14135 queries.
14 Correct 179 ms 420 KB Guessed the password with 14141 queries.
15 Correct 197 ms 480 KB Guessed the password with 15122 queries.
16 Correct 176 ms 480 KB Guessed the password with 15189 queries.
17 Correct 157 ms 508 KB Guessed the password with 15441 queries.
18 Correct 215 ms 632 KB Guessed the password with 15401 queries.
19 Correct 210 ms 632 KB Guessed the password with 15913 queries.
20 Correct 231 ms 504 KB Guessed the password with 15982 queries.
21 Correct 198 ms 392 KB Guessed the password with 15531 queries.
22 Correct 225 ms 384 KB Guessed the password with 15498 queries.
23 Correct 310 ms 544 KB Guessed the password with 22417 queries.
24 Correct 307 ms 656 KB Guessed the password with 22285 queries.
25 Correct 310 ms 420 KB Guessed the password with 23631 queries.
26 Correct 321 ms 428 KB Guessed the password with 23380 queries.
27 Correct 341 ms 656 KB Guessed the password with 23921 queries.
28 Correct 332 ms 524 KB Guessed the password with 23505 queries.
29 Correct 342 ms 768 KB Guessed the password with 24076 queries.
30 Correct 356 ms 616 KB Guessed the password with 23352 queries.