oj.uz

Submission #287014

# Submission time Handle Problem Language Result Execution time Memory
287014 2020-08-31T08:57:55 Z crossing0ver Password (RMI18_password) C++17
50 / 100
 560 ms 636 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());
vector<char> D;
bool check(int x) {
/*	string P = pref + D[x];
	P += suf;
	if (P.size() <= n) {
		int z = query(P);
		if (z > cur ) 
			return 1;
	}
	return 0;*/
	return 0;
}
string guess(int n, int s) {
	string 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);
	/*	int lo = max((pref.size() ? mp[pref.back()] : 0),(suf.size() ? mp[suf[0]] : 0));
		int hi = s-1;
		while (lo < hi) {
			int mid = (lo + hi)/2;
			if (check(mid))
		}*/
		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) {
			//if (pref.size() + suf.size() + 1 == n) {
			P = pref + c;
			P += suf;
			int F = query(P);
			if (F > cur) {
				LAST = c;
				pref += c;
				cur = F;
				flag  = 1;
				break;
		//	}
		}/*else if (pref.size() + suf.size() + 2 <= n){
			P = pref + c;
			P += c;
			P += suf;
			int F = query(P);
			if (F > cur + 1) {
				LAST = c;
				pref += c;
				pref += c;
				cur = F;
				flag  = 1;
				break;
			}else 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:36:34: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |  for (; pref.size() + suf.size() < n; ) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
password.cpp:41:48: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |   for (int z = 1; z + pref.size() + suf.size() <= n;) {
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:97:32: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |   if (pref.size() + suf.size() == n) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:99:8: warning: unused variable 'Z' [-Wunused-variable]
   99 |    int Z = query(pref);
      |        ^
password.cpp:38:8: warning: variable 'LAST' set but not used [-Wunused-but-set-variable]
   38 |   char LAST = ((int)pref.size() ? pref.back() : 'a');
      |        ^~~~
password.cpp:35:7: warning: unused variable 'fs' [-Wunused-variable]
   35 |  char fs = 'a';
      |       ^~
password.cpp:104:6: warning: unused variable 'z' [-Wunused-variable]
  104 |  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 132 queries.
2 Correct 3 ms 256 KB Guessed the password with 318 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 217 queries.
3 Correct 2 ms 256 KB Guessed the password with 123 queries.
4 Correct 4 ms 256 KB Guessed the password with 354 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 380 KB Guessed the password with 7872 queries.
2 Correct 126 ms 376 KB Guessed the password with 11607 queries.
3 Correct 198 ms 380 KB Guessed the password with 16880 queries.
4 Correct 177 ms 380 KB Guessed the password with 26195 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 132 queries.
2 Correct 3 ms 256 KB Guessed the password with 318 queries.
3 Correct 2 ms 256 KB Guessed the password with 115 queries.
4 Correct 3 ms 256 KB Guessed the password with 217 queries.
5 Correct 2 ms 256 KB Guessed the password with 123 queries.
6 Correct 4 ms 256 KB Guessed the password with 354 queries.
7 Correct 87 ms 380 KB Guessed the password with 7872 queries.
8 Correct 126 ms 376 KB Guessed the password with 11607 queries.
9 Correct 198 ms 380 KB Guessed the password with 16880 queries.
10 Correct 177 ms 380 KB Guessed the password with 26195 queries.
11 Correct 453 ms 508 KB Guessed the password with 42259 queries.
12 Correct 360 ms 636 KB Guessed the password with 36577 queries.
13 Incorrect 560 ms 508 KB Could not guess the password with 50000 queries.
14 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 132 queries.
2 Correct 3 ms 256 KB Guessed the password with 318 queries.
3 Correct 2 ms 256 KB Guessed the password with 115 queries.
4 Correct 3 ms 256 KB Guessed the password with 217 queries.
5 Correct 2 ms 256 KB Guessed the password with 123 queries.
6 Correct 4 ms 256 KB Guessed the password with 354 queries.
7 Correct 87 ms 380 KB Guessed the password with 7872 queries.
8 Correct 126 ms 376 KB Guessed the password with 11607 queries.
9 Correct 198 ms 380 KB Guessed the password with 16880 queries.
10 Correct 177 ms 380 KB Guessed the password with 26195 queries.
11 Correct 453 ms 508 KB Guessed the password with 42259 queries.
12 Correct 360 ms 636 KB Guessed the password with 36577 queries.
13 Incorrect 560 ms 508 KB Could not guess the password with 50000 queries.
14 Halted 0 ms 0 KB -