Submission #519410

#	Time	Username	Problem	Language	Result	Execution time	Memory
519410		hohohaha	Password (RMI18_password)	C++14	100 / 100	258 ms	580 KiB

password

#include<bits/stdc++.h> 
using namespace std;
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); i--)
//#define fi first
//#define se second
//#define all(x) begin(x), end(x)
//#define ii pair<int, int>
//#define pb push_back
//#define pf push_front
//#define em emplace
//#define ef emplace_front
//#define eb emplace_back
//#define om pop
//#define of pop_front
//#define ob pop_back
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 
//#define rand rng
#define endl '\n'
#define sp ' '

int cnt[26]; 
int query(string); 
string handle(int l, int r) { 
	if(l == r) { 
		string re; 
		char c = char(l + 'a'); 
		fori(i, 1, cnt[l]) re.push_back(c); 
		//cout << re << endl; 
		return re; 
	}
	else { 
		int m = l + r >> 1; 
		string L = handle(l, m);
		string R = handle(m + 1, r); 
		int q_num = 0, len = L.size() + R.size();
		int ptr = 0; 
		for(char C: R) { 
			while(1) { 
				if(ptr == L.size()) { 	
					L.insert(ptr, 1, C); 
					ptr++; 
					break; 
				}
				string tempL = L; tempL.insert(ptr, 1, C); 
				++q_num; assert(q_num <= len); 
				if(query(tempL) == tempL.size()) { 
					L = tempL; ptr++; 
					break; 
				}
				else { 
					ptr++; 
				}
			}
		}
		//cout << L << endl; 
		return L; 
	}
}
string guess(int n, int s)  { 
	fori(i, 0, s - 1) { 
		char c = char(i + 'a'); 
		string q; 
		fori(j, 1, n) q.push_back(c); 
		cnt[i] = query(q);
	}
	return handle(0, s - 1); 
}

Compilation message (stderr)

password.cpp: In function 'std::string handle(int, int)':
password.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int m = l + r >> 1;
      |           ~~^~~
password.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if(ptr == L.size()) {
      |        ~~~~^~~~~~~~~~~
password.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if(query(tempL) == tempL.size()) {
      |        ~~~~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20