oj.uz

Submission #709090

# Submission time Handle Problem Language Result Execution time Memory
709090 2023-03-13T06:10:19 Z jamezzz Password (RMI18_password) C++17
50 / 100
 485 ms 484 KB 
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(time(0));

int query(string str);

string guess(int n,int s){
	string ans="";
	int pv=0;
	vector<int> v;
	for(int i=0;i<s;++i)v.push_back(i);
	shuffle(v.begin(),v.end(),rng);
	for(int i:v){
		char c='a'+i;
		for(int j=0;j<ans.length();++j){
			string tmp=ans;
			tmp.insert(j,1,c);
			int res=query(tmp);
			if(res>pv){
				pv=res;
				swap(tmp,ans);
				tmp.clear();
				if(pv==n)return ans;
				continue;
			}
			else tmp.clear();
		}
		string tmp=ans;
		tmp.insert(tmp.length(),n-tmp.length(),c);
		pv=query(tmp);
		tmp.resize(pv);
		swap(ans,tmp);
		tmp.clear();
		if(pv==n)return ans;
	}
	return ans;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for(int j=0;j<ans.length();++j){
      |               ~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 126 queries.
2 Correct 3 ms 208 KB Guessed the password with 286 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 47 queries.
2 Correct 1 ms 208 KB Guessed the password with 90 queries.
3 Correct 2 ms 208 KB Guessed the password with 168 queries.
4 Correct 3 ms 308 KB Guessed the password with 226 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 348 KB Guessed the password with 5308 queries.
2 Correct 96 ms 352 KB Guessed the password with 10138 queries.
3 Correct 142 ms 352 KB Guessed the password with 15026 queries.
4 Correct 147 ms 460 KB Guessed the password with 20933 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 126 queries.
2 Correct 3 ms 208 KB Guessed the password with 286 queries.
3 Correct 1 ms 208 KB Guessed the password with 47 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 2 ms 208 KB Guessed the password with 168 queries.
6 Correct 3 ms 308 KB Guessed the password with 226 queries.
7 Correct 28 ms 348 KB Guessed the password with 5308 queries.
8 Correct 96 ms 352 KB Guessed the password with 10138 queries.
9 Correct 142 ms 352 KB Guessed the password with 15026 queries.
10 Correct 147 ms 460 KB Guessed the password with 20933 queries.
11 Correct 322 ms 368 KB Guessed the password with 35542 queries.
12 Correct 387 ms 360 KB Guessed the password with 30575 queries.
13 Correct 344 ms 368 KB Guessed the password with 36479 queries.
14 Correct 468 ms 440 KB Guessed the password with 45871 queries.
15 Correct 227 ms 484 KB Guessed the password with 32053 queries.
16 Correct 237 ms 368 KB Guessed the password with 28563 queries.
17 Incorrect 485 ms 328 KB Could not guess the password with 50000 queries.
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 126 queries.
2 Correct 3 ms 208 KB Guessed the password with 286 queries.
3 Correct 1 ms 208 KB Guessed the password with 47 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 2 ms 208 KB Guessed the password with 168 queries.
6 Correct 3 ms 308 KB Guessed the password with 226 queries.
7 Correct 28 ms 348 KB Guessed the password with 5308 queries.
8 Correct 96 ms 352 KB Guessed the password with 10138 queries.
9 Correct 142 ms 352 KB Guessed the password with 15026 queries.
10 Correct 147 ms 460 KB Guessed the password with 20933 queries.
11 Correct 322 ms 368 KB Guessed the password with 35542 queries.
12 Correct 387 ms 360 KB Guessed the password with 30575 queries.
13 Correct 344 ms 368 KB Guessed the password with 36479 queries.
14 Correct 468 ms 440 KB Guessed the password with 45871 queries.
15 Correct 227 ms 484 KB Guessed the password with 32053 queries.
16 Correct 237 ms 368 KB Guessed the password with 28563 queries.
17 Incorrect 485 ms 328 KB Could not guess the password with 50000 queries.
18 Halted 0 ms 0 KB -