oj.uz

Submission #286985

# Submission time Handle Problem Language Result Execution time Memory
286985 2020-08-31T08:28:01 Z crossing0ver Password (RMI18_password) C++17
50 / 100
 585 ms 512 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 134 queries.
2 Correct 4 ms 256 KB Guessed the password with 316 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 115 queries.
2 Correct 3 ms 256 KB Guessed the password with 236 queries.
3 Correct 1 ms 256 KB Guessed the password with 96 queries.
4 Correct 4 ms 256 KB Guessed the password with 414 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 256 KB Guessed the password with 8686 queries.
2 Correct 132 ms 256 KB Guessed the password with 11566 queries.
3 Correct 129 ms 504 KB Guessed the password with 10954 queries.
4 Correct 188 ms 376 KB Guessed the password with 22681 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 134 queries.
2 Correct 4 ms 256 KB Guessed the password with 316 queries.
3 Correct 2 ms 256 KB Guessed the password with 115 queries.
4 Correct 3 ms 256 KB Guessed the password with 236 queries.
5 Correct 1 ms 256 KB Guessed the password with 96 queries.
6 Correct 4 ms 256 KB Guessed the password with 414 queries.
7 Correct 86 ms 256 KB Guessed the password with 8686 queries.
8 Correct 132 ms 256 KB Guessed the password with 11566 queries.
9 Correct 129 ms 504 KB Guessed the password with 10954 queries.
10 Correct 188 ms 376 KB Guessed the password with 22681 queries.
11 Correct 466 ms 380 KB Guessed the password with 49663 queries.
12 Correct 243 ms 384 KB Guessed the password with 25410 queries.
13 Correct 318 ms 508 KB Guessed the password with 35891 queries.
14 Correct 431 ms 384 KB Guessed the password with 41814 queries.
15 Correct 408 ms 512 KB Guessed the password with 47918 queries.
16 Correct 511 ms 508 KB Guessed the password with 48248 queries.
17 Correct 574 ms 388 KB Guessed the password with 44832 queries.
18 Incorrect 585 ms 388 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 134 queries.
2 Correct 4 ms 256 KB Guessed the password with 316 queries.
3 Correct 2 ms 256 KB Guessed the password with 115 queries.
4 Correct 3 ms 256 KB Guessed the password with 236 queries.
5 Correct 1 ms 256 KB Guessed the password with 96 queries.
6 Correct 4 ms 256 KB Guessed the password with 414 queries.
7 Correct 86 ms 256 KB Guessed the password with 8686 queries.
8 Correct 132 ms 256 KB Guessed the password with 11566 queries.
9 Correct 129 ms 504 KB Guessed the password with 10954 queries.
10 Correct 188 ms 376 KB Guessed the password with 22681 queries.
11 Correct 466 ms 380 KB Guessed the password with 49663 queries.
12 Correct 243 ms 384 KB Guessed the password with 25410 queries.
13 Correct 318 ms 508 KB Guessed the password with 35891 queries.
14 Correct 431 ms 384 KB Guessed the password with 41814 queries.
15 Correct 408 ms 512 KB Guessed the password with 47918 queries.
16 Correct 511 ms 508 KB Guessed the password with 48248 queries.
17 Correct 574 ms 388 KB Guessed the password with 44832 queries.
18 Incorrect 585 ms 388 KB Could not guess the password with 50000 queries.
19 Halted 0 ms 0 KB -