| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1310334 | ycled_t12 | Combo (IOI18_combo) | C++17 | 0 ms | 0 KiB |
// Ready-to-submit implementation for IOI 2018 - Combo
// If you want to test locally, compile with -DLOCAL
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
// --- Local simulator for testing ---
// Define a press() that reads the secret S from stdin (first line) and simulates judge.
static string SECRET;
static int PRESS_COUNT = 0;
int press(const string &p) {
++PRESS_COUNT;
// longest prefix of SECRET that appears as a substring of p
int N = (int)SECRET.size();
int best = 0;
for (int len = 0; len <= N; ++len) {
string pref = SECRET.substr(0, len);
if (pref.empty()) { best = max(best, 0); continue; }
if ((int)pref.size() > (int)p.size()) break;
if (p.find(pref) != string::npos) best = max(best, len);
}
return best;
}
string guess_sequence(int N);
int main() {
if (!getline(cin, SECRET)) return 0;
// trim newline
while (!SECRET.empty() && (SECRET.back() == '\r' || SECRET.back() == '\n')) SECRET.pop_back();
int N = (int)SECRET.size();
string ans = guess_sequence(N);
cerr << "press calls: " << PRESS_COUNT << "\n";
cout << ans << "\n";
return 0;
}
#else
// In judge/submission environment the header provides press(string).
// Uncomment the next line if your judge requires #include "combo.h"
// #include "combo.h"
// declare press to satisfy compiler (the real one is provided by grader)
extern int press(const string &p);
string guess_sequence(int N);
#endif
// --- Implementation of the editorial algorithm ---
string guess_sequence(int N) {
string s = "";
// 1) determine first character with up to 3 presses
// try "AB" to detect whether first char is A/B or X/Y
int r = press(string("AB"));
if (r > 0) {
// first char is A or B
int r2 = press(string("A"));
if (r2 > 0) s = "A";
else s = "B";
} else {
// first char is X or Y
int r2 = press(string("X"));
if (r2 > 0) s = "X";
else s = "Y";
}
if (N == 1) return s;
// prepare the three other letters (in order p1, p2, p3)
vector<char> all = {'A','B','X','Y'};
char f = s[0];
vector<char> p;
for (char c : all) if (c != f) p.push_back(c);
// p[0], p[1], p[2] are the three candidates in some fixed order
// 2) determine positions 2..N-1 (1-based indexing) using the concatenation trick
// loop i from 2 to N-1 (inclusive). At loop start s.length() == i-1.
for (int i = 2; i <= N-1; ++i) {
// construct query string exactly as in the editorial:
// G = s + p1 + s + (p2 + p1) + s + (p2 + p2) + s + (p2 + p3)
// (characters p1/p2/p3 correspond to p[0],p[1],p[2])
string G;
G.reserve(4 * s.size() + 6);
G += s;
G.push_back(p[0]);
G += s;
G.push_back(p[1]);
G.push_back(p[0]);
G += s;
G.push_back(p[1]);
G.push_back(p[1]);
G += s;
G.push_back(p[1]);
G.push_back(p[2]);
int coins = press(G);
// coins is the length of the longest prefix of SECRET that appears in G.
// At this stage s.size() == i-1.
if (coins == i) {
// next char is p1
s.push_back(p[0]);
} else if (coins == i-1) {
// next char is p3
s.push_back(p[2]);
} else {
// otherwise next char is p2
s.push_back(p[1]);
}
}
// 3) determine last character (position N) using up to 2 presses
// Try s + p1; if returns N then p1 is last character; else try p2; otherwise p3.
if ((int)s.size() < N) {
string G = s;
G.push_back(p[0]);
int coins = press(G);
if (coins == N) {
s.push_back(p[0]);
} else {
G = s;
G.push_back(p[1]);
coins = press(G);
if (coins == N) s.push_back(p[1]);
else s.push_back(p[2]);
}
}
return s;
}