oj.uz

Submission #286982

# Submission time Handle Problem Language Result Execution time Memory
286982 2020-08-31T08:25:07 Z crossing0ver Password (RMI18_password) C++17
50 / 100
 599 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 142 queries.
2 Correct 3 ms 256 KB Guessed the password with 277 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 2 ms 256 KB Guessed the password with 168 queries.
3 Correct 2 ms 256 KB Guessed the password with 126 queries.
4 Correct 4 ms 256 KB Guessed the password with 333 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 384 KB Guessed the password with 8033 queries.
2 Correct 88 ms 256 KB Guessed the password with 11995 queries.
3 Correct 167 ms 384 KB Guessed the password with 14522 queries.
4 Correct 202 ms 380 KB Guessed the password with 20328 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 142 queries.
2 Correct 3 ms 256 KB Guessed the password with 277 queries.
3 Correct 2 ms 256 KB Guessed the password with 115 queries.
4 Correct 2 ms 256 KB Guessed the password with 168 queries.
5 Correct 2 ms 256 KB Guessed the password with 126 queries.
6 Correct 4 ms 256 KB Guessed the password with 333 queries.
7 Correct 90 ms 384 KB Guessed the password with 8033 queries.
8 Correct 88 ms 256 KB Guessed the password with 11995 queries.
9 Correct 167 ms 384 KB Guessed the password with 14522 queries.
10 Correct 202 ms 380 KB Guessed the password with 20328 queries.
11 Correct 374 ms 504 KB Guessed the password with 33789 queries.
12 Correct 446 ms 632 KB Guessed the password with 42175 queries.
13 Correct 518 ms 384 KB Guessed the password with 46156 queries.
14 Incorrect 599 ms 384 KB Could not guess the password with 50000 queries.
15 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 142 queries.
2 Correct 3 ms 256 KB Guessed the password with 277 queries.
3 Correct 2 ms 256 KB Guessed the password with 115 queries.
4 Correct 2 ms 256 KB Guessed the password with 168 queries.
5 Correct 2 ms 256 KB Guessed the password with 126 queries.
6 Correct 4 ms 256 KB Guessed the password with 333 queries.
7 Correct 90 ms 384 KB Guessed the password with 8033 queries.
8 Correct 88 ms 256 KB Guessed the password with 11995 queries.
9 Correct 167 ms 384 KB Guessed the password with 14522 queries.
10 Correct 202 ms 380 KB Guessed the password with 20328 queries.
11 Correct 374 ms 504 KB Guessed the password with 33789 queries.
12 Correct 446 ms 632 KB Guessed the password with 42175 queries.
13 Correct 518 ms 384 KB Guessed the password with 46156 queries.
14 Incorrect 599 ms 384 KB Could not guess the password with 50000 queries.
15 Halted 0 ms 0 KB -