oj.uz

Submission #287144

# Submission time Handle Problem Language Result Execution time Memory
287144 2020-08-31T12:35:57 Z crossing0ver Password (RMI18_password) C++17
50 / 100
 670 ms 760 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<string> sub(27);
int par[27];
int PAR(int x) {
	if (par[x] == x) return x;
	return PAR(par[x]);
}
void removeF(string &s){
	reverse(all(s));
	if (s.size())
	s.pop_back();
	reverse(all(s));
	return;
}
void join(int x,int y) {
	x = PAR(x), y = PAR(y);
	if (sub[x].size() > sub[y].size())
		swap(x,y);
	par[x] = y;
	int tot = sub[x].size() + sub[y].size();
	string pref;
	int cur = sub[y].size();
	for (int i = 0;pref.size() < tot && i < sub[x].size(); i++) {
		string P = pref + sub[x][i];
		P += sub[y];
		//int F;
		int F = query(P);
		if (F > cur) {
			pref += sub[x][i];
			cur = F;
		}else {
			if (sub[y].size()) {
			pref += sub[y][0];
			removeF(sub[y]);
			i--;
		}
		}
	}
	sub[y] = pref + sub[y];
//	if (query(sub[y]) != (int)sub[y].size() || (int)sub[y].size() != tot)
	//	while(true) {
			
	//	}
}
string guess(int n, int s) {
	string pref,P;
	for (int i = 0;i < s; i++) {
		par[i] = i;
		for (int j = 0; j < n; j++)
		P+=('a'+ i);
		//int x;
		int x = query(P);
		P.clear();
		for (int j = 0; j < x; j++)
			P+=('a' + i);
		sub[i] = P;
		P.clear();
	}
	for (int i = 1; i < s; i++) {
		join(i,0);
	}
	int x = PAR(0);
	query(sub[x]);
	return sub[x];
	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 'void join(int, int)':
password.cpp:36:29: 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 (int i = 0;pref.size() < tot && i < sub[x].size(); i++) {
      |                 ~~~~~~~~~~~~^~~~~
password.cpp:36:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i = 0;pref.size() < tot && i < sub[x].size(); i++) {
      |                                      ~~^~~~~~~~~~~~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:85:34: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |  for (; pref.size() + suf.size() < n; ) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
password.cpp:90:48: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |   for (int z = 1; z + pref.size() + suf.size() <= n;) {
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:118:32: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |   if (pref.size() + suf.size() == n) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:120:8: warning: unused variable 'Z' [-Wunused-variable]
  120 |    int Z = query(pref);
      |        ^
password.cpp:87:8: warning: variable 'LAST' set but not used [-Wunused-but-set-variable]
   87 |   char LAST = ((int)pref.size() ? pref.back() : 'a');
      |        ^~~~
password.cpp:84:7: warning: unused variable 'fs' [-Wunused-variable]
   84 |  char fs = 'a';
      |       ^~
password.cpp:125:6: warning: unused variable 'z' [-Wunused-variable]
  125 |  int z = query(pref);
      |      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 76 queries.
2 Correct 2 ms 256 KB Guessed the password with 187 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 52 queries.
2 Correct 3 ms 384 KB Guessed the password with 116 queries.
3 Correct 4 ms 256 KB Guessed the password with 105 queries.
4 Correct 3 ms 384 KB Guessed the password with 216 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 384 KB Guessed the password with 4513 queries.
2 Correct 139 ms 384 KB Guessed the password with 10191 queries.
3 Correct 157 ms 504 KB Guessed the password with 12507 queries.
4 Correct 229 ms 504 KB Guessed the password with 20416 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 76 queries.
2 Correct 2 ms 256 KB Guessed the password with 187 queries.
3 Correct 1 ms 256 KB Guessed the password with 52 queries.
4 Correct 3 ms 384 KB Guessed the password with 116 queries.
5 Correct 4 ms 256 KB Guessed the password with 105 queries.
6 Correct 3 ms 384 KB Guessed the password with 216 queries.
7 Correct 65 ms 384 KB Guessed the password with 4513 queries.
8 Correct 139 ms 384 KB Guessed the password with 10191 queries.
9 Correct 157 ms 504 KB Guessed the password with 12507 queries.
10 Correct 229 ms 504 KB Guessed the password with 20416 queries.
11 Correct 670 ms 632 KB Guessed the password with 49512 queries.
12 Correct 139 ms 632 KB Guessed the password with 11393 queries.
13 Correct 639 ms 668 KB Guessed the password with 47683 queries.
14 Correct 216 ms 760 KB Guessed the password with 21361 queries.
15 Correct 600 ms 640 KB Guessed the password with 44836 queries.
16 Correct 196 ms 520 KB Guessed the password with 17934 queries.
17 Execution timed out 627 ms 512 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 76 queries.
2 Correct 2 ms 256 KB Guessed the password with 187 queries.
3 Correct 1 ms 256 KB Guessed the password with 52 queries.
4 Correct 3 ms 384 KB Guessed the password with 116 queries.
5 Correct 4 ms 256 KB Guessed the password with 105 queries.
6 Correct 3 ms 384 KB Guessed the password with 216 queries.
7 Correct 65 ms 384 KB Guessed the password with 4513 queries.
8 Correct 139 ms 384 KB Guessed the password with 10191 queries.
9 Correct 157 ms 504 KB Guessed the password with 12507 queries.
10 Correct 229 ms 504 KB Guessed the password with 20416 queries.
11 Correct 670 ms 632 KB Guessed the password with 49512 queries.
12 Correct 139 ms 632 KB Guessed the password with 11393 queries.
13 Correct 639 ms 668 KB Guessed the password with 47683 queries.
14 Correct 216 ms 760 KB Guessed the password with 21361 queries.
15 Correct 600 ms 640 KB Guessed the password with 44836 queries.
16 Correct 196 ms 520 KB Guessed the password with 17934 queries.
17 Execution timed out 627 ms 512 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -