oj.uz

Submission #286963

# Submission time Handle Problem Language Result Execution time Memory
286963 2020-08-31T08:10:03 Z crossing0ver Password (RMI18_password) C++17
50 / 100
 581 ms 508 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;

int m;
string suf,pref;
int query(string str);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string guess(int n, int s) {
	string pref,P;
	vector<char> T;
	for (char i = 'a'; i < 'a' + s ; i++)
		T.pb(i);
	char fs = 'a';
	for (; pref.size() + suf.size() <= n; ) {
		int len = suf.size() + pref.size();
		char LAST = ((int)pref.size() ? pref.back() : 'a');
		int cur = len;
		vector<char> D = T;
		for (int z = 1; z + pref.size() + suf.size() <= n;) {
			bool flag = 0;
			vector<char> Q;
			shuffle(D.begin(),D.end(),rng);
		for (char c = (suf.size() ? suf[0] : 'a'); c < 'a' + s; c++){
	///	for (char c : D) {
			P = pref + c;
			P += suf;
			int F = query(P);
			if (F > cur) {
				LAST = c;
				pref += c;
				cur = F;
				flag  = 1;
				break;
			}
		//	else Q.pb(c);
		}
	//	for (char c :  Q) D.erase(find(all(D),c));
		if (flag == 0) break;
		}
		reverse(all(suf));
		if (pref.size())
		suf+=pref.back();
		reverse(all(suf));
		if (pref.size())
		pref.pop_back();
		if (pref.size() + suf.size() == n) {
			pref += suf;
			int Z = query(pref);
			return pref;
		}
	}
	pref += suf;
	int z = query(pref);
	return pref;
}
/*
main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

}*/

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:21:34: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |  for (; pref.size() + suf.size() <= n; ) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:26:48: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |   for (int z = 1; z + pref.size() + suf.size() <= n;) {
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:53:32: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |   if (pref.size() + suf.size() == n) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:55:8: warning: unused variable 'Z' [-Wunused-variable]
   55 |    int Z = query(pref);
      |        ^
password.cpp:23:8: warning: variable 'LAST' set but not used [-Wunused-but-set-variable]
   23 |   char LAST = ((int)pref.size() ? pref.back() : 'a');
      |        ^~~~
password.cpp:20:7: warning: unused variable 'fs' [-Wunused-variable]
   20 |  char fs = 'a';
      |       ^~
password.cpp:60:6: warning: unused variable 'z' [-Wunused-variable]
   60 |  int z = query(pref);
      |      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 204 queries.
2 Correct 6 ms 256 KB Guessed the password with 451 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 145 queries.
2 Correct 3 ms 256 KB Guessed the password with 272 queries.
3 Correct 3 ms 256 KB Guessed the password with 282 queries.
4 Correct 5 ms 256 KB Guessed the password with 452 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 508 KB Guessed the password with 8850 queries.
2 Correct 190 ms 372 KB Guessed the password with 16776 queries.
3 Correct 237 ms 256 KB Guessed the password with 24761 queries.
4 Correct 295 ms 504 KB Guessed the password with 33736 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 204 queries.
2 Correct 6 ms 256 KB Guessed the password with 451 queries.
3 Correct 2 ms 256 KB Guessed the password with 145 queries.
4 Correct 3 ms 256 KB Guessed the password with 272 queries.
5 Correct 3 ms 256 KB Guessed the password with 282 queries.
6 Correct 5 ms 256 KB Guessed the password with 452 queries.
7 Correct 68 ms 508 KB Guessed the password with 8850 queries.
8 Correct 190 ms 372 KB Guessed the password with 16776 queries.
9 Correct 237 ms 256 KB Guessed the password with 24761 queries.
10 Correct 295 ms 504 KB Guessed the password with 33736 queries.
11 Incorrect 581 ms 376 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 2 ms 256 KB Guessed the password with 204 queries.
2 Correct 6 ms 256 KB Guessed the password with 451 queries.
3 Correct 2 ms 256 KB Guessed the password with 145 queries.
4 Correct 3 ms 256 KB Guessed the password with 272 queries.
5 Correct 3 ms 256 KB Guessed the password with 282 queries.
6 Correct 5 ms 256 KB Guessed the password with 452 queries.
7 Correct 68 ms 508 KB Guessed the password with 8850 queries.
8 Correct 190 ms 372 KB Guessed the password with 16776 queries.
9 Correct 237 ms 256 KB Guessed the password with 24761 queries.
10 Correct 295 ms 504 KB Guessed the password with 33736 queries.
11 Incorrect 581 ms 376 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -