oj.uz

Submission #855657

# Submission time Handle Problem Language Result Execution time Memory
855657 2023-10-01T16:01:15 Z franfill Password (RMI18_password) C++17
50 / 100
 253 ms 1496 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 oldsize = cur.size();
				solve(i, us, rv);
				int newsize = cur.size();
				solve(newsize-(oldsize-(i+1)), 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);
	reverse(cur.begin(), cur.end());
	solve(cur.size(), us, true);
	reverse(cur.begin(), cur.end());
	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())
      |        ~~~~~~~~~~~~~~^~~~~~~~~~~~

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 436 KB Guessed the password with 116 queries.
2 Correct 1 ms 436 KB Guessed the password with 232 queries.
3 Correct 1 ms 440 KB Guessed the password with 199 queries.
4 Correct 2 ms 432 KB Guessed the password with 328 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1236 KB Guessed the password with 5793 queries.
2 Correct 56 ms 1440 KB Guessed the password with 12045 queries.
3 Correct 75 ms 1496 KB Guessed the password with 15980 queries.
4 Correct 107 ms 1312 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 436 KB Guessed the password with 116 queries.
4 Correct 1 ms 436 KB Guessed the password with 232 queries.
5 Correct 1 ms 440 KB Guessed the password with 199 queries.
6 Correct 2 ms 432 KB Guessed the password with 328 queries.
7 Correct 27 ms 1236 KB Guessed the password with 5793 queries.
8 Correct 56 ms 1440 KB Guessed the password with 12045 queries.
9 Correct 75 ms 1496 KB Guessed the password with 15980 queries.
10 Correct 107 ms 1312 KB Guessed the password with 22882 queries.
11 Incorrect 253 ms 1324 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 436 KB Guessed the password with 116 queries.
4 Correct 1 ms 436 KB Guessed the password with 232 queries.
5 Correct 1 ms 440 KB Guessed the password with 199 queries.
6 Correct 2 ms 432 KB Guessed the password with 328 queries.
7 Correct 27 ms 1236 KB Guessed the password with 5793 queries.
8 Correct 56 ms 1440 KB Guessed the password with 12045 queries.
9 Correct 75 ms 1496 KB Guessed the password with 15980 queries.
10 Correct 107 ms 1312 KB Guessed the password with 22882 queries.
11 Incorrect 253 ms 1324 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -