oj.uz

Submission #519410

# Submission time Handle Problem Language Result Execution time Memory
519410 2022-01-26T10:26:03 Z hohohaha Password (RMI18_password) C++14
100 / 100
 258 ms 580 KB 
#include<bits/stdc++.h> 
using namespace std;
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); i--)
//#define fi first
//#define se second
//#define all(x) begin(x), end(x)
//#define ii pair<int, int>
//#define pb push_back
//#define pf push_front
//#define em emplace
//#define ef emplace_front
//#define eb emplace_back
//#define om pop
//#define of pop_front
//#define ob pop_back
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 
//#define rand rng
#define endl '\n'
#define sp ' '

int cnt[26]; 
int query(string); 
string handle(int l, int r) { 
	if(l == r) { 
		string re; 
		char c = char(l + 'a'); 
		fori(i, 1, cnt[l]) re.push_back(c); 
		//cout << re << endl; 
		return re; 
	}
	else { 
		int m = l + r >> 1; 
		string L = handle(l, m);
		string R = handle(m + 1, r); 
		int q_num = 0, len = L.size() + R.size();
		int ptr = 0; 
		for(char C: R) { 
			while(1) { 
				if(ptr == L.size()) { 	
					L.insert(ptr, 1, C); 
					ptr++; 
					break; 
				}
				string tempL = L; tempL.insert(ptr, 1, C); 
				++q_num; assert(q_num <= len); 
				if(query(tempL) == tempL.size()) { 
					L = tempL; ptr++; 
					break; 
				}
				else { 
					ptr++; 
				}
			}
		}
		//cout << L << endl; 
		return L; 
	}
}
string guess(int n, int s)  { 
	fori(i, 0, s - 1) { 
		char c = char(i + 'a'); 
		string q; 
		fori(j, 1, n) q.push_back(c); 
		cnt[i] = query(q);
	}
	return handle(0, s - 1); 
}

Compilation message

password.cpp: In function 'std::string handle(int, int)':
password.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int m = l + r >> 1;
      |           ~~^~~
password.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if(ptr == L.size()) {
      |        ~~~~^~~~~~~~~~~
password.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if(query(tempL) == tempL.size()) {
      |        ~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 60 queries.
2 Correct 2 ms 200 KB Guessed the password with 100 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 48 queries.
2 Correct 2 ms 200 KB Guessed the password with 116 queries.
3 Correct 1 ms 200 KB Guessed the password with 91 queries.
4 Correct 2 ms 200 KB Guessed the password with 198 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 304 KB Guessed the password with 3455 queries.
2 Correct 53 ms 312 KB Guessed the password with 5024 queries.
3 Correct 62 ms 420 KB Guessed the password with 6353 queries.
4 Correct 75 ms 416 KB Guessed the password with 8694 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 60 queries.
2 Correct 2 ms 200 KB Guessed the password with 100 queries.
3 Correct 1 ms 200 KB Guessed the password with 48 queries.
4 Correct 2 ms 200 KB Guessed the password with 116 queries.
5 Correct 1 ms 200 KB Guessed the password with 91 queries.
6 Correct 2 ms 200 KB Guessed the password with 198 queries.
7 Correct 33 ms 304 KB Guessed the password with 3455 queries.
8 Correct 53 ms 312 KB Guessed the password with 5024 queries.
9 Correct 62 ms 420 KB Guessed the password with 6353 queries.
10 Correct 75 ms 416 KB Guessed the password with 8694 queries.
11 Correct 128 ms 324 KB Guessed the password with 13637 queries.
12 Correct 106 ms 464 KB Guessed the password with 12460 queries.
13 Correct 149 ms 320 KB Guessed the password with 14391 queries.
14 Correct 112 ms 580 KB Guessed the password with 13938 queries.
15 Correct 163 ms 328 KB Guessed the password with 15072 queries.
16 Correct 125 ms 448 KB Guessed the password with 14153 queries.
17 Correct 170 ms 312 KB Guessed the password with 16053 queries.
18 Correct 153 ms 440 KB Guessed the password with 15190 queries.
19 Correct 142 ms 568 KB Guessed the password with 16409 queries.
20 Correct 131 ms 460 KB Guessed the password with 14248 queries.
21 Correct 183 ms 332 KB Guessed the password with 16848 queries.
22 Correct 152 ms 452 KB Guessed the password with 15316 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 60 queries.
2 Correct 2 ms 200 KB Guessed the password with 100 queries.
3 Correct 1 ms 200 KB Guessed the password with 48 queries.
4 Correct 2 ms 200 KB Guessed the password with 116 queries.
5 Correct 1 ms 200 KB Guessed the password with 91 queries.
6 Correct 2 ms 200 KB Guessed the password with 198 queries.
7 Correct 33 ms 304 KB Guessed the password with 3455 queries.
8 Correct 53 ms 312 KB Guessed the password with 5024 queries.
9 Correct 62 ms 420 KB Guessed the password with 6353 queries.
10 Correct 75 ms 416 KB Guessed the password with 8694 queries.
11 Correct 128 ms 324 KB Guessed the password with 13637 queries.
12 Correct 106 ms 464 KB Guessed the password with 12460 queries.
13 Correct 149 ms 320 KB Guessed the password with 14391 queries.
14 Correct 112 ms 580 KB Guessed the password with 13938 queries.
15 Correct 163 ms 328 KB Guessed the password with 15072 queries.
16 Correct 125 ms 448 KB Guessed the password with 14153 queries.
17 Correct 170 ms 312 KB Guessed the password with 16053 queries.
18 Correct 153 ms 440 KB Guessed the password with 15190 queries.
19 Correct 142 ms 568 KB Guessed the password with 16409 queries.
20 Correct 131 ms 460 KB Guessed the password with 14248 queries.
21 Correct 183 ms 332 KB Guessed the password with 16848 queries.
22 Correct 152 ms 452 KB Guessed the password with 15316 queries.
23 Correct 258 ms 448 KB Guessed the password with 23613 queries.
24 Correct 224 ms 452 KB Guessed the password with 22227 queries.
25 Correct 204 ms 388 KB Guessed the password with 23795 queries.
26 Correct 169 ms 444 KB Guessed the password with 23333 queries.
27 Correct 162 ms 500 KB Guessed the password with 23764 queries.
28 Correct 236 ms 340 KB Guessed the password with 23044 queries.
29 Correct 158 ms 408 KB Guessed the password with 23848 queries.
30 Correct 203 ms 444 KB Guessed the password with 22507 queries.