oj.uz

Submission #286965

# Submission time Handle Problem Language Result Execution time Memory
286965 2020-08-31T08:11:37 Z crossing0ver Password (RMI18_password) C++17
50 / 100
 433 ms 504 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 = (pref.size() ? pref.back() : '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 3 ms 256 KB Guessed the password with 194 queries.
2 Correct 5 ms 256 KB Guessed the password with 444 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 129 queries.
2 Correct 3 ms 256 KB Guessed the password with 261 queries.
3 Correct 2 ms 256 KB Guessed the password with 127 queries.
4 Correct 4 ms 256 KB Guessed the password with 389 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 376 KB Guessed the password with 7482 queries.
2 Correct 136 ms 376 KB Guessed the password with 14116 queries.
3 Correct 223 ms 504 KB Guessed the password with 22723 queries.
4 Correct 322 ms 504 KB Guessed the password with 30773 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Guessed the password with 194 queries.
2 Correct 5 ms 256 KB Guessed the password with 444 queries.
3 Correct 2 ms 256 KB Guessed the password with 129 queries.
4 Correct 3 ms 256 KB Guessed the password with 261 queries.
5 Correct 2 ms 256 KB Guessed the password with 127 queries.
6 Correct 4 ms 256 KB Guessed the password with 389 queries.
7 Correct 72 ms 376 KB Guessed the password with 7482 queries.
8 Correct 136 ms 376 KB Guessed the password with 14116 queries.
9 Correct 223 ms 504 KB Guessed the password with 22723 queries.
10 Correct 322 ms 504 KB Guessed the password with 30773 queries.
11 Incorrect 433 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 3 ms 256 KB Guessed the password with 194 queries.
2 Correct 5 ms 256 KB Guessed the password with 444 queries.
3 Correct 2 ms 256 KB Guessed the password with 129 queries.
4 Correct 3 ms 256 KB Guessed the password with 261 queries.
5 Correct 2 ms 256 KB Guessed the password with 127 queries.
6 Correct 4 ms 256 KB Guessed the password with 389 queries.
7 Correct 72 ms 376 KB Guessed the password with 7482 queries.
8 Correct 136 ms 376 KB Guessed the password with 14116 queries.
9 Correct 223 ms 504 KB Guessed the password with 22723 queries.
10 Correct 322 ms 504 KB Guessed the password with 30773 queries.
11 Incorrect 433 ms 376 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -