oj.uz

Submission #709246

# Submission time Handle Problem Language Result Execution time Memory
709246 2023-03-13T09:28:25 Z hmm789 Password (RMI18_password) C++14
80 / 100
 1335 ms 556 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string s);
string guess(int n, int s) {
	int cnt = 1;
	string ans = "";
	pair<int, int> occ[s];
	for(int i = 0; i < s; i++) {
		string s;
		for(int j = 0; j < n; j++) s += (char)('a'+i);
		occ[i].first = query(s);
		occ[i].second = i;
		//~ cout << "a " << i << " " << l-1 << endl;
	}
	sort(occ, occ+s);
	for(int i = 0; i < occ[0].first; i++) ans += (char)('a'+occ[0].second);
	for(int i = 1; i < s; i++) {
		//~ cout << "s" << i << ": " << ans << endl;
		int tmpcnt[ans.size()+1], sm = 0;
		memset(tmpcnt, 0, sizeof(tmpcnt));
		for(int j = ans.size(); j >= 0; j--) {
			string tmp = "";
			for(int k = 0; k < j; k++) tmp += ans[k];
			for(int k = 0; k < n-j; k++) tmp += (char)('a'+occ[i].second);
			int tmp2 = query(tmp);
			tmpcnt[j] = tmp2-sm-j;
			sm += tmpcnt[j];
		}
		string tmp = "";
		for(int j = 0; j < ans.size(); j++) tmp += ans[j];
		//~ cout << "s" << i << ": " <<  tmp << endl;
		ans = "";
		for(int j = 0; j < tmpcnt[0]; j++) ans += (char)('a'+occ[i].second);
		for(int j = 1; j <= tmp.size(); j++) {
			//~ cout << "s" << i << "(" << j << "): " << ans << endl;
			ans += tmp[j-1];
			for(int k = 0; k < tmpcnt[j]; k++) ans += (char)('a'+occ[i].second);
		}
		//~ cout << "s" << i << ": " << ans << endl;
	}
	return ans;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int j = 0; j < ans.size(); j++) tmp += ans[j];
      |                  ~~^~~~~~~~~~~~
password.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int j = 1; j <= tmp.size(); j++) {
      |                  ~~^~~~~~~~~~~~~
password.cpp:6:6: warning: unused variable 'cnt' [-Wunused-variable]
    6 |  int cnt = 1;
      |      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 135 queries.
2 Correct 2 ms 208 KB Guessed the password with 299 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 28 queries.
2 Correct 1 ms 208 KB Guessed the password with 34 queries.
3 Correct 1 ms 208 KB Guessed the password with 20 queries.
4 Correct 1 ms 208 KB Guessed the password with 93 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 208 KB Guessed the password with 2160 queries.
2 Correct 124 ms 284 KB Guessed the password with 8449 queries.
3 Correct 52 ms 336 KB Guessed the password with 3638 queries.
4 Correct 274 ms 292 KB Guessed the password with 12061 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 135 queries.
2 Correct 2 ms 208 KB Guessed the password with 299 queries.
3 Correct 1 ms 208 KB Guessed the password with 28 queries.
4 Correct 1 ms 208 KB Guessed the password with 34 queries.
5 Correct 1 ms 208 KB Guessed the password with 20 queries.
6 Correct 1 ms 208 KB Guessed the password with 93 queries.
7 Correct 35 ms 208 KB Guessed the password with 2160 queries.
8 Correct 124 ms 284 KB Guessed the password with 8449 queries.
9 Correct 52 ms 336 KB Guessed the password with 3638 queries.
10 Correct 274 ms 292 KB Guessed the password with 12061 queries.
11 Correct 161 ms 300 KB Guessed the password with 6648 queries.
12 Correct 181 ms 300 KB Guessed the password with 6681 queries.
13 Correct 383 ms 300 KB Guessed the password with 15007 queries.
14 Correct 417 ms 296 KB Guessed the password with 15385 queries.
15 Correct 303 ms 300 KB Guessed the password with 11319 queries.
16 Correct 311 ms 424 KB Guessed the password with 11223 queries.
17 Correct 236 ms 296 KB Guessed the password with 8978 queries.
18 Correct 262 ms 316 KB Guessed the password with 9060 queries.
19 Correct 213 ms 292 KB Guessed the password with 7637 queries.
20 Correct 216 ms 296 KB Guessed the password with 7860 queries.
21 Correct 330 ms 308 KB Guessed the password with 11829 queries.
22 Correct 321 ms 304 KB Guessed the password with 11947 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 135 queries.
2 Correct 2 ms 208 KB Guessed the password with 299 queries.
3 Correct 1 ms 208 KB Guessed the password with 28 queries.
4 Correct 1 ms 208 KB Guessed the password with 34 queries.
5 Correct 1 ms 208 KB Guessed the password with 20 queries.
6 Correct 1 ms 208 KB Guessed the password with 93 queries.
7 Correct 35 ms 208 KB Guessed the password with 2160 queries.
8 Correct 124 ms 284 KB Guessed the password with 8449 queries.
9 Correct 52 ms 336 KB Guessed the password with 3638 queries.
10 Correct 274 ms 292 KB Guessed the password with 12061 queries.
11 Correct 161 ms 300 KB Guessed the password with 6648 queries.
12 Correct 181 ms 300 KB Guessed the password with 6681 queries.
13 Correct 383 ms 300 KB Guessed the password with 15007 queries.
14 Correct 417 ms 296 KB Guessed the password with 15385 queries.
15 Correct 303 ms 300 KB Guessed the password with 11319 queries.
16 Correct 311 ms 424 KB Guessed the password with 11223 queries.
17 Correct 236 ms 296 KB Guessed the password with 8978 queries.
18 Correct 262 ms 316 KB Guessed the password with 9060 queries.
19 Correct 213 ms 292 KB Guessed the password with 7637 queries.
20 Correct 216 ms 296 KB Guessed the password with 7860 queries.
21 Correct 330 ms 308 KB Guessed the password with 11829 queries.
22 Correct 321 ms 304 KB Guessed the password with 11947 queries.
23 Execution timed out 1335 ms 556 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -