oj.uz

Submission #1069977

# Submission time Handle Problem Language Result Execution time Memory
1069977 2024-08-22T10:47:12 Z AdamGS Password (RMI18_password) C++17
100 / 100
 226 ms 1872 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
int query(string p);
string guess(int n, int s) {
	vector<pair<int,string>>A;
	rep(i, s) {
		string p="";
		rep(j, n) p+=char(i+'a');
		int x=query(p);
		while(p.size()>x) p.pop_back();
		if(x) A.pb({x, p});
	}
	while(A.size()>1) {
		sort(all(A));
		reverse(all(A));
		string a=A[A.size()-1].nd, b=A[A.size()-2].nd;
		A.pop_back(); A.pop_back();
		int l=0;
		string ans="";
		for(auto i : a) {
			string x=ans;
			x+=i;
			for(int j=l; j<b.size(); ++j) x+=b[j];
			while(query(x)<x.size()) {
				ans+=b[l];
				++l;
				x=ans;
				x+=i;
				for(int j=l; j<b.size(); ++j) x+=b[j];
			}
			ans+=i;
		}
		while(l<b.size()) {
			ans+=b[l];
			++l;
		}
		A.pb({ans.size(), ans});
	}
	return A[0].nd;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:16:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |   while(p.size()>x) p.pop_back();
      |         ~~~~~~~~^~
password.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |    for(int j=l; j<b.size(); ++j) x+=b[j];
      |                 ~^~~~~~~~~
password.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    while(query(x)<x.size()) {
      |          ~~~~~~~~^~~~~~~~~
password.cpp:35:19: 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=l; j<b.size(); ++j) x+=b[j];
      |                  ~^~~~~~~~~
password.cpp:39:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   while(l<b.size()) {
      |         ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 69 queries.
2 Correct 1 ms 344 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 52 queries.
2 Correct 1 ms 344 KB Guessed the password with 92 queries.
3 Correct 1 ms 344 KB Guessed the password with 105 queries.
4 Correct 1 ms 344 KB Guessed the password with 179 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 700 KB Guessed the password with 2764 queries.
2 Correct 31 ms 448 KB Guessed the password with 5079 queries.
3 Correct 30 ms 712 KB Guessed the password with 4592 queries.
4 Correct 64 ms 448 KB Guessed the password with 8147 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 69 queries.
2 Correct 1 ms 344 KB Guessed the password with 111 queries.
3 Correct 1 ms 344 KB Guessed the password with 52 queries.
4 Correct 1 ms 344 KB Guessed the password with 92 queries.
5 Correct 1 ms 344 KB Guessed the password with 105 queries.
6 Correct 1 ms 344 KB Guessed the password with 179 queries.
7 Correct 23 ms 700 KB Guessed the password with 2764 queries.
8 Correct 31 ms 448 KB Guessed the password with 5079 queries.
9 Correct 30 ms 712 KB Guessed the password with 4592 queries.
10 Correct 64 ms 448 KB Guessed the password with 8147 queries.
11 Correct 74 ms 984 KB Guessed the password with 8174 queries.
12 Correct 67 ms 708 KB Guessed the password with 8176 queries.
13 Correct 91 ms 728 KB Guessed the password with 11521 queries.
14 Correct 89 ms 856 KB Guessed the password with 11625 queries.
15 Correct 84 ms 984 KB Guessed the password with 10894 queries.
16 Correct 80 ms 848 KB Guessed the password with 10882 queries.
17 Correct 99 ms 600 KB Guessed the password with 10226 queries.
18 Correct 94 ms 600 KB Guessed the password with 10292 queries.
19 Correct 98 ms 728 KB Guessed the password with 9704 queries.
20 Correct 83 ms 740 KB Guessed the password with 9794 queries.
21 Correct 99 ms 484 KB Guessed the password with 11694 queries.
22 Correct 98 ms 708 KB Guessed the password with 11776 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 69 queries.
2 Correct 1 ms 344 KB Guessed the password with 111 queries.
3 Correct 1 ms 344 KB Guessed the password with 52 queries.
4 Correct 1 ms 344 KB Guessed the password with 92 queries.
5 Correct 1 ms 344 KB Guessed the password with 105 queries.
6 Correct 1 ms 344 KB Guessed the password with 179 queries.
7 Correct 23 ms 700 KB Guessed the password with 2764 queries.
8 Correct 31 ms 448 KB Guessed the password with 5079 queries.
9 Correct 30 ms 712 KB Guessed the password with 4592 queries.
10 Correct 64 ms 448 KB Guessed the password with 8147 queries.
11 Correct 74 ms 984 KB Guessed the password with 8174 queries.
12 Correct 67 ms 708 KB Guessed the password with 8176 queries.
13 Correct 91 ms 728 KB Guessed the password with 11521 queries.
14 Correct 89 ms 856 KB Guessed the password with 11625 queries.
15 Correct 84 ms 984 KB Guessed the password with 10894 queries.
16 Correct 80 ms 848 KB Guessed the password with 10882 queries.
17 Correct 99 ms 600 KB Guessed the password with 10226 queries.
18 Correct 94 ms 600 KB Guessed the password with 10292 queries.
19 Correct 98 ms 728 KB Guessed the password with 9704 queries.
20 Correct 83 ms 740 KB Guessed the password with 9794 queries.
21 Correct 99 ms 484 KB Guessed the password with 11694 queries.
22 Correct 98 ms 708 KB Guessed the password with 11776 queries.
23 Correct 207 ms 1332 KB Guessed the password with 23728 queries.
24 Correct 201 ms 1004 KB Guessed the password with 20992 queries.
25 Correct 205 ms 748 KB Guessed the password with 23694 queries.
26 Correct 198 ms 764 KB Guessed the password with 19164 queries.
27 Correct 226 ms 988 KB Guessed the password with 23773 queries.
28 Correct 191 ms 916 KB Guessed the password with 16842 queries.
29 Correct 220 ms 1228 KB Guessed the password with 23733 queries.
30 Correct 136 ms 1872 KB Guessed the password with 14402 queries.