Submission #945473

# Submission time Handle Problem Language Result Execution time Memory
945473 2024-03-13T23:09:53 Z thunopro Password (RMI18_password) C++14
100 / 100
127 ms 1860 KB
#include<bits/stdc++.h>
using namespace std ; 
#define maxn 200009
#define ll long long 
#define pb push_back 
#define fi first 
#define se second 
//#define left id<<1
//#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1 
#define TIME ( 1.0*clock() / CLOCKS_PER_SEC )
const int mod = 1e9+7 ;
const int INF = 1e9 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a >= mod ) a -= mod ; 
	if ( a < 0 ) a += mod ; 
}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ;
}

mt19937 rng (time(0)) ; 

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}
int cnt [26] ; 

extern int query ( string s ) ; 
string dc ( int l , int r ) 
{
	if ( l == r ) 
	{
		string res (cnt[l],'a'+l) ; 
		return res ; 
	}
	int mid = (l+r)/2 ; 
	string left = dc (l,mid) , right = dc (mid+1,r) ; 
	if ( left.size () == 0 ) return right ; 
	if ( right.size () == 0 ) return left ; 
	string res = "" ; 
	int i = 0 , j = 0 ; 
	while ( i<left.size() && j<right.size() ) 
	{
		int len = query (res+left[i]+right.substr(j)) ; 
		int base = res.size () + right.size() - j ;
		if ( len > base ) res += left [i++] ; 
		else res += right [j++] ; 
	}
	if ( i < left.size () ) res += left.substr (i) ; 
	else res += right.substr (j) ; 
	
	return res ; 
}
string guess ( int n , int s ) 
{
	for ( int i = 0 ; i < s ; i ++ ) 
	{
		string str (n,'a'+i) ; 
		cnt [i] = query (str) ; 
	}
	return dc (0,s-1) ; 
}
//int main () 
//{
//	ios_base::sync_with_stdio(0); 
//	cin.tie(0);cout.tie(0); 
////	rf () ;
//}

Compilation message

password.cpp: In function 'std::string dc(int, int)':
password.cpp:60:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  while ( i<left.size() && j<right.size() )
      |          ~^~~~~~~~~~~~
password.cpp:60:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  while ( i<left.size() && j<right.size() )
      |                           ~^~~~~~~~~~~~~
password.cpp:67:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  if ( i < left.size () ) res += left.substr (i) ;
      |       ~~^~~~~~~~~~~~~~
password.cpp: In function 'void rf()':
password.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 61 queries.
2 Correct 1 ms 344 KB Guessed the password with 101 queries.
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Guessed the password with 49 queries.
2 Correct 1 ms 344 KB Guessed the password with 117 queries.
3 Correct 1 ms 344 KB Guessed the password with 92 queries.
4 Correct 1 ms 440 KB Guessed the password with 197 queries.
# Verdict Execution time Memory Grader output
1 Correct 17 ms 948 KB Guessed the password with 3456 queries.
2 Correct 24 ms 960 KB Guessed the password with 5025 queries.
3 Correct 26 ms 704 KB Guessed the password with 6352 queries.
4 Correct 53 ms 724 KB Guessed the password with 8693 queries.
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 61 queries.
2 Correct 1 ms 344 KB Guessed the password with 101 queries.
3 Correct 0 ms 344 KB Guessed the password with 49 queries.
4 Correct 1 ms 344 KB Guessed the password with 117 queries.
5 Correct 1 ms 344 KB Guessed the password with 92 queries.
6 Correct 1 ms 440 KB Guessed the password with 197 queries.
7 Correct 17 ms 948 KB Guessed the password with 3456 queries.
8 Correct 24 ms 960 KB Guessed the password with 5025 queries.
9 Correct 26 ms 704 KB Guessed the password with 6352 queries.
10 Correct 53 ms 724 KB Guessed the password with 8693 queries.
11 Correct 72 ms 720 KB Guessed the password with 13638 queries.
12 Correct 59 ms 732 KB Guessed the password with 12459 queries.
13 Correct 68 ms 1224 KB Guessed the password with 14392 queries.
14 Correct 69 ms 964 KB Guessed the password with 13937 queries.
15 Correct 71 ms 964 KB Guessed the password with 15073 queries.
16 Correct 84 ms 728 KB Guessed the password with 14154 queries.
17 Correct 83 ms 708 KB Guessed the password with 16054 queries.
18 Correct 71 ms 968 KB Guessed the password with 15189 queries.
19 Correct 84 ms 968 KB Guessed the password with 16410 queries.
20 Correct 68 ms 1208 KB Guessed the password with 14247 queries.
21 Correct 101 ms 936 KB Guessed the password with 16849 queries.
22 Correct 69 ms 728 KB Guessed the password with 15315 queries.
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 61 queries.
2 Correct 1 ms 344 KB Guessed the password with 101 queries.
3 Correct 0 ms 344 KB Guessed the password with 49 queries.
4 Correct 1 ms 344 KB Guessed the password with 117 queries.
5 Correct 1 ms 344 KB Guessed the password with 92 queries.
6 Correct 1 ms 440 KB Guessed the password with 197 queries.
7 Correct 17 ms 948 KB Guessed the password with 3456 queries.
8 Correct 24 ms 960 KB Guessed the password with 5025 queries.
9 Correct 26 ms 704 KB Guessed the password with 6352 queries.
10 Correct 53 ms 724 KB Guessed the password with 8693 queries.
11 Correct 72 ms 720 KB Guessed the password with 13638 queries.
12 Correct 59 ms 732 KB Guessed the password with 12459 queries.
13 Correct 68 ms 1224 KB Guessed the password with 14392 queries.
14 Correct 69 ms 964 KB Guessed the password with 13937 queries.
15 Correct 71 ms 964 KB Guessed the password with 15073 queries.
16 Correct 84 ms 728 KB Guessed the password with 14154 queries.
17 Correct 83 ms 708 KB Guessed the password with 16054 queries.
18 Correct 71 ms 968 KB Guessed the password with 15189 queries.
19 Correct 84 ms 968 KB Guessed the password with 16410 queries.
20 Correct 68 ms 1208 KB Guessed the password with 14247 queries.
21 Correct 101 ms 936 KB Guessed the password with 16849 queries.
22 Correct 69 ms 728 KB Guessed the password with 15315 queries.
23 Correct 127 ms 1836 KB Guessed the password with 23612 queries.
24 Correct 119 ms 1860 KB Guessed the password with 22226 queries.
25 Correct 116 ms 1140 KB Guessed the password with 23794 queries.
26 Correct 122 ms 1584 KB Guessed the password with 23332 queries.
27 Correct 115 ms 1560 KB Guessed the password with 23763 queries.
28 Correct 110 ms 1292 KB Guessed the password with 23045 queries.
29 Correct 113 ms 1348 KB Guessed the password with 23847 queries.
30 Correct 106 ms 1508 KB Guessed the password with 22506 queries.