oj.uz

Submission #286970

# Submission time Handle Problem Language Result Execution time Memory
286970 2020-08-31T08:15:50 Z crossing0ver Password (RMI18_password) C++17
50 / 100
 564 ms 516 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);
	random_shuffle(all(D));
	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 128 queries.
2 Correct 4 ms 256 KB Guessed the password with 307 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 243 queries.
3 Correct 2 ms 256 KB Guessed the password with 123 queries.
4 Correct 5 ms 256 KB Guessed the password with 333 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 384 KB Guessed the password with 9404 queries.
2 Correct 120 ms 504 KB Guessed the password with 11399 queries.
3 Correct 186 ms 376 KB Guessed the password with 16644 queries.
4 Correct 257 ms 376 KB Guessed the password with 23333 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 128 queries.
2 Correct 4 ms 256 KB Guessed the password with 307 queries.
3 Correct 2 ms 256 KB Guessed the password with 120 queries.
4 Correct 3 ms 256 KB Guessed the password with 243 queries.
5 Correct 2 ms 256 KB Guessed the password with 123 queries.
6 Correct 5 ms 256 KB Guessed the password with 333 queries.
7 Correct 105 ms 384 KB Guessed the password with 9404 queries.
8 Correct 120 ms 504 KB Guessed the password with 11399 queries.
9 Correct 186 ms 376 KB Guessed the password with 16644 queries.
10 Correct 257 ms 376 KB Guessed the password with 23333 queries.
11 Correct 442 ms 384 KB Guessed the password with 44170 queries.
12 Correct 392 ms 508 KB Guessed the password with 41909 queries.
13 Correct 521 ms 504 KB Guessed the password with 46252 queries.
14 Correct 463 ms 512 KB Guessed the password with 44987 queries.
15 Incorrect 564 ms 516 KB Could not guess the password with 50000 queries.
16 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 128 queries.
2 Correct 4 ms 256 KB Guessed the password with 307 queries.
3 Correct 2 ms 256 KB Guessed the password with 120 queries.
4 Correct 3 ms 256 KB Guessed the password with 243 queries.
5 Correct 2 ms 256 KB Guessed the password with 123 queries.
6 Correct 5 ms 256 KB Guessed the password with 333 queries.
7 Correct 105 ms 384 KB Guessed the password with 9404 queries.
8 Correct 120 ms 504 KB Guessed the password with 11399 queries.
9 Correct 186 ms 376 KB Guessed the password with 16644 queries.
10 Correct 257 ms 376 KB Guessed the password with 23333 queries.
11 Correct 442 ms 384 KB Guessed the password with 44170 queries.
12 Correct 392 ms 508 KB Guessed the password with 41909 queries.
13 Correct 521 ms 504 KB Guessed the password with 46252 queries.
14 Correct 463 ms 512 KB Guessed the password with 44987 queries.
15 Incorrect 564 ms 516 KB Could not guess the password with 50000 queries.
16 Halted 0 ms 0 KB -