oj.uz

Submission #287145

# Submission time Handle Problem Language Result Execution time Memory
287145 2020-08-31T12:41:10 Z crossing0ver Password (RMI18_password) C++17
100 / 100
 302 ms 744 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;
}
set<pii> H;
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();
	H.erase({(int)sub[x].size(),x});
	H.erase({(int)sub[y].size(),y});
	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--;
		}
		}
	}
	H.insert({tot,y});
	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  = 0; i < s; i++) {
		H.insert({sub[i].size(),i});
	}
	while (H.size() >= 2) {
		auto it = H.begin();
	int  x = it->se;
	it++;
	int y = it->se;
	join(x,y);
	}
	int x = PAR(H.begin()->se);
	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:39:29: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |  for (int i = 0;pref.size() < tot && i < sub[x].size(); i++) {
      |                 ~~~~~~~~~~~~^~~~~
password.cpp:39:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0;pref.size() < tot && i < sub[x].size(); i++) {
      |                                      ~~^~~~~~~~~~~~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:96:34: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |  for (; pref.size() + suf.size() < n; ) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
password.cpp:101:48: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |   for (int z = 1; z + pref.size() + suf.size() <= n;) {
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:129:32: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  129 |   if (pref.size() + suf.size() == n) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:131:8: warning: unused variable 'Z' [-Wunused-variable]
  131 |    int Z = query(pref);
      |        ^
password.cpp:98:8: warning: variable 'LAST' set but not used [-Wunused-but-set-variable]
   98 |   char LAST = ((int)pref.size() ? pref.back() : 'a');
      |        ^~~~
password.cpp:95:7: warning: unused variable 'fs' [-Wunused-variable]
   95 |  char fs = 'a';
      |       ^~
password.cpp:136:6: warning: unused variable 'z' [-Wunused-variable]
  136 |  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 69 queries.
2 Correct 2 ms 384 KB Guessed the password with 111 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 1 ms 256 KB Guessed the password with 92 queries.
3 Correct 2 ms 256 KB Guessed the password with 105 queries.
4 Correct 2 ms 256 KB Guessed the password with 179 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 384 KB Guessed the password with 2764 queries.
2 Correct 35 ms 504 KB Guessed the password with 5079 queries.
3 Correct 62 ms 380 KB Guessed the password with 4592 queries.
4 Correct 68 ms 504 KB Guessed the password with 8147 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 69 queries.
2 Correct 2 ms 384 KB Guessed the password with 111 queries.
3 Correct 1 ms 256 KB Guessed the password with 52 queries.
4 Correct 1 ms 256 KB Guessed the password with 92 queries.
5 Correct 2 ms 256 KB Guessed the password with 105 queries.
6 Correct 2 ms 256 KB Guessed the password with 179 queries.
7 Correct 35 ms 384 KB Guessed the password with 2764 queries.
8 Correct 35 ms 504 KB Guessed the password with 5079 queries.
9 Correct 62 ms 380 KB Guessed the password with 4592 queries.
10 Correct 68 ms 504 KB Guessed the password with 8147 queries.
11 Correct 81 ms 508 KB Guessed the password with 8173 queries.
12 Correct 82 ms 632 KB Guessed the password with 8178 queries.
13 Correct 125 ms 520 KB Guessed the password with 11521 queries.
14 Correct 137 ms 504 KB Guessed the password with 11625 queries.
15 Correct 125 ms 504 KB Guessed the password with 10894 queries.
16 Correct 107 ms 504 KB Guessed the password with 10883 queries.
17 Correct 130 ms 508 KB Guessed the password with 10226 queries.
18 Correct 136 ms 384 KB Guessed the password with 10285 queries.
19 Correct 130 ms 384 KB Guessed the password with 9704 queries.
20 Correct 130 ms 384 KB Guessed the password with 9795 queries.
21 Correct 143 ms 512 KB Guessed the password with 11694 queries.
22 Correct 171 ms 504 KB Guessed the password with 11776 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 69 queries.
2 Correct 2 ms 384 KB Guessed the password with 111 queries.
3 Correct 1 ms 256 KB Guessed the password with 52 queries.
4 Correct 1 ms 256 KB Guessed the password with 92 queries.
5 Correct 2 ms 256 KB Guessed the password with 105 queries.
6 Correct 2 ms 256 KB Guessed the password with 179 queries.
7 Correct 35 ms 384 KB Guessed the password with 2764 queries.
8 Correct 35 ms 504 KB Guessed the password with 5079 queries.
9 Correct 62 ms 380 KB Guessed the password with 4592 queries.
10 Correct 68 ms 504 KB Guessed the password with 8147 queries.
11 Correct 81 ms 508 KB Guessed the password with 8173 queries.
12 Correct 82 ms 632 KB Guessed the password with 8178 queries.
13 Correct 125 ms 520 KB Guessed the password with 11521 queries.
14 Correct 137 ms 504 KB Guessed the password with 11625 queries.
15 Correct 125 ms 504 KB Guessed the password with 10894 queries.
16 Correct 107 ms 504 KB Guessed the password with 10883 queries.
17 Correct 130 ms 508 KB Guessed the password with 10226 queries.
18 Correct 136 ms 384 KB Guessed the password with 10285 queries.
19 Correct 130 ms 384 KB Guessed the password with 9704 queries.
20 Correct 130 ms 384 KB Guessed the password with 9795 queries.
21 Correct 143 ms 512 KB Guessed the password with 11694 queries.
22 Correct 171 ms 504 KB Guessed the password with 11776 queries.
23 Correct 273 ms 696 KB Guessed the password with 23728 queries.
24 Correct 290 ms 576 KB Guessed the password with 20992 queries.
25 Correct 280 ms 540 KB Guessed the password with 23694 queries.
26 Correct 279 ms 572 KB Guessed the password with 19161 queries.
27 Correct 302 ms 436 KB Guessed the password with 23773 queries.
28 Correct 230 ms 744 KB Guessed the password with 16842 queries.
29 Correct 285 ms 580 KB Guessed the password with 23733 queries.
30 Correct 175 ms 692 KB Guessed the password with 14403 queries.