oj.uz

Submission #286984

# Submission time Handle Problem Language Result Execution time Memory
286984 2020-08-31T08:26:52 Z crossing0ver Password (RMI18_password) C++17
50 / 100
 488 ms 632 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> D;
	for (char i = 'a'; i < 'a' + s ; i++)
		D.pb(i);
	shuffle(all(D),rng);
	map<char,int> mp;
	for (int i = 0;i < s; i++) mp[D[i]] = 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 (int  b= max((pref.size() ? mp[pref.back()] : 0),(suf.size() ? mp[suf[0]] : 0)); b < s; b++){
			char c = D[b];
	///	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:24:34: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |  for (; pref.size() + suf.size() < n; ) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
password.cpp:29:48: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |   for (int z = 1; z + pref.size() + suf.size() <= n;) {
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:57:32: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |   if (pref.size() + suf.size() == n) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:59:8: warning: unused variable 'Z' [-Wunused-variable]
   59 |    int Z = query(pref);
      |        ^
password.cpp:26:8: warning: variable 'LAST' set but not used [-Wunused-but-set-variable]
   26 |   char LAST = ((int)pref.size() ? pref.back() : 'a');
      |        ^~~~
password.cpp:23:7: warning: unused variable 'fs' [-Wunused-variable]
   23 |  char fs = 'a';
      |       ^~
password.cpp:64:6: warning: unused variable 'z' [-Wunused-variable]
   64 |  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 148 queries.
2 Correct 3 ms 256 KB Guessed the password with 300 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 120 queries.
2 Correct 3 ms 256 KB Guessed the password with 236 queries.
3 Correct 2 ms 384 KB Guessed the password with 92 queries.
4 Correct 4 ms 288 KB Guessed the password with 313 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 500 KB Guessed the password with 7884 queries.
2 Correct 128 ms 376 KB Guessed the password with 11834 queries.
3 Correct 177 ms 376 KB Guessed the password with 16230 queries.
4 Correct 205 ms 632 KB Guessed the password with 22516 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 148 queries.
2 Correct 3 ms 256 KB Guessed the password with 300 queries.
3 Correct 2 ms 256 KB Guessed the password with 120 queries.
4 Correct 3 ms 256 KB Guessed the password with 236 queries.
5 Correct 2 ms 384 KB Guessed the password with 92 queries.
6 Correct 4 ms 288 KB Guessed the password with 313 queries.
7 Correct 58 ms 500 KB Guessed the password with 7884 queries.
8 Correct 128 ms 376 KB Guessed the password with 11834 queries.
9 Correct 177 ms 376 KB Guessed the password with 16230 queries.
10 Correct 205 ms 632 KB Guessed the password with 22516 queries.
11 Correct 488 ms 632 KB Guessed the password with 47112 queries.
12 Correct 325 ms 512 KB Guessed the password with 39085 queries.
13 Correct 433 ms 420 KB Guessed the password with 46383 queries.
14 Correct 347 ms 508 KB Guessed the password with 37145 queries.
15 Correct 364 ms 380 KB Guessed the password with 40153 queries.
16 Correct 437 ms 504 KB Guessed the password with 48956 queries.
17 Correct 346 ms 388 KB Guessed the password with 38596 queries.
18 Incorrect 442 ms 384 KB Could not guess the password with 50000 queries.
19 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 148 queries.
2 Correct 3 ms 256 KB Guessed the password with 300 queries.
3 Correct 2 ms 256 KB Guessed the password with 120 queries.
4 Correct 3 ms 256 KB Guessed the password with 236 queries.
5 Correct 2 ms 384 KB Guessed the password with 92 queries.
6 Correct 4 ms 288 KB Guessed the password with 313 queries.
7 Correct 58 ms 500 KB Guessed the password with 7884 queries.
8 Correct 128 ms 376 KB Guessed the password with 11834 queries.
9 Correct 177 ms 376 KB Guessed the password with 16230 queries.
10 Correct 205 ms 632 KB Guessed the password with 22516 queries.
11 Correct 488 ms 632 KB Guessed the password with 47112 queries.
12 Correct 325 ms 512 KB Guessed the password with 39085 queries.
13 Correct 433 ms 420 KB Guessed the password with 46383 queries.
14 Correct 347 ms 508 KB Guessed the password with 37145 queries.
15 Correct 364 ms 380 KB Guessed the password with 40153 queries.
16 Correct 437 ms 504 KB Guessed the password with 48956 queries.
17 Correct 346 ms 388 KB Guessed the password with 38596 queries.
18 Incorrect 442 ms 384 KB Could not guess the password with 50000 queries.
19 Halted 0 ms 0 KB -