Submission #242555

#	Time	Username	Problem	Language	Result	Execution time	Memory
242555		tjd229	Password (RMI18_password)	C++14	100 / 100	285 ms	800 KiB

password

#include <string>
using namespace std;

extern int query(string str);
int cnt[26];

string dc(int s,int e) {
	if (s == e) {
		string res(cnt[s], 'a' + s);
		return res;
	}
	int m = (s + e) >> 1;
	string left = dc(s, m);
	string right = dc(m + 1, e);
	if (left.size() == 0) return right;
	if (right.size() == 0) return left;
	string res = "";
	int l = 0, r = 0;
	while (l < left.size() && r < right.size()) {
		int len = query(res + left[l] + right.substr(r));
		int base = res.size() + right.size() - r;
		if (len > base) res += left[l++];
		else res += right[r++];
	}
	if (l < left.size()) res += left.substr(l);
	else res += right.substr(r);
	
	return res;
}
string guess(int n, int s) {
	for (int i = 0; i < s; ++i) {
		string str(n, 'a' + i);
		cnt[i] = query(str);
	}

	return dc(0,s-1);
}

Compilation message (stderr)

password.cpp: In function 'std::__cxx11::string dc(int, int)':
password.cpp:20:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (l < left.size() && r < right.size()) {
         ~~^~~~~~~~~~~~~
password.cpp:20:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (l < left.size() && r < right.size()) {
                            ~~^~~~~~~~~~~~~~
password.cpp:26:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (l < left.size()) res += left.substr(l);
      ~~^~~~~~~~~~~~~

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