oj.uz

Submission #855658

# Submission time Handle Problem Language Result Execution time Memory
855658 2023-10-01T16:02:54 Z franfill Password (RMI18_password) C++17
50 / 100
 257 ms 2040 KB 
#include<bits/stdc++.h>
using namespace std;

int query(string S);

int query(string S, bool rv)
{
	if (rv)
		reverse(S.begin(), S.end());
	return query(S);
}

string cur = "";
int N, S;

void solve(int i, vector < bool > us, bool rv = false)
{
	if (cur.size() == N)
		return;
	for (int c = 0; c < S; c++)
		if (us[c])
		{
			string tr = cur.substr(0, i);	
			tr += char('a'+c);
			tr += cur.substr(i, cur.size()-i);
			if (query(tr, rv) == tr.size())
			{
				cur = tr;
				int d = (int)cur.size() - (i+1);
				solve(i, us, rv);
				int newsize = cur.size();
				solve(((int)cur.size()-d), us, rv);
				return;
			}
			else
				us[c] = false;
		}
}

string guess(int N, int S)
{	
	::N = N;
	::S = S;
	cur = "";
	vector < bool > us(S, true);
	solve(0, us, false);
	return cur;
}

Compilation message

password.cpp: In function 'void solve(int, std::vector<bool>, bool)':
password.cpp:18:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |  if (cur.size() == N)
      |      ~~~~~~~~~~~^~~~
password.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    if (query(tr, rv) == tr.size())
      |        ~~~~~~~~~~~~~~^~~~~~~~~~~~
password.cpp:31:9: warning: unused variable 'newsize' [-Wunused-variable]
   31 |     int newsize = cur.size();
      |         ^~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Guessed the password with 116 queries.
2 Correct 2 ms 436 KB Guessed the password with 232 queries.
3 Correct 1 ms 436 KB Guessed the password with 199 queries.
4 Correct 2 ms 692 KB Guessed the password with 328 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2040 KB Guessed the password with 5793 queries.
2 Correct 62 ms 1496 KB Guessed the password with 12045 queries.
3 Correct 83 ms 1228 KB Guessed the password with 15980 queries.
4 Correct 117 ms 1584 KB Guessed the password with 22882 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 135 queries.
2 Correct 1 ms 344 KB Guessed the password with 289 queries.
3 Correct 1 ms 432 KB Guessed the password with 116 queries.
4 Correct 2 ms 436 KB Guessed the password with 232 queries.
5 Correct 1 ms 436 KB Guessed the password with 199 queries.
6 Correct 2 ms 692 KB Guessed the password with 328 queries.
7 Correct 27 ms 2040 KB Guessed the password with 5793 queries.
8 Correct 62 ms 1496 KB Guessed the password with 12045 queries.
9 Correct 83 ms 1228 KB Guessed the password with 15980 queries.
10 Correct 117 ms 1584 KB Guessed the password with 22882 queries.
11 Incorrect 257 ms 1316 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 135 queries.
2 Correct 1 ms 344 KB Guessed the password with 289 queries.
3 Correct 1 ms 432 KB Guessed the password with 116 queries.
4 Correct 2 ms 436 KB Guessed the password with 232 queries.
5 Correct 1 ms 436 KB Guessed the password with 199 queries.
6 Correct 2 ms 692 KB Guessed the password with 328 queries.
7 Correct 27 ms 2040 KB Guessed the password with 5793 queries.
8 Correct 62 ms 1496 KB Guessed the password with 12045 queries.
9 Correct 83 ms 1228 KB Guessed the password with 15980 queries.
10 Correct 117 ms 1584 KB Guessed the password with 22882 queries.
11 Incorrect 257 ms 1316 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -