| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1302752 | baodat | 콤보 (IOI18_combo) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, l, r) for(int i = l; i <= (int)r; i++)
#define FORD(i, l, r) for(int i = l; i >= (int)r; i--)
#define aint(x) (x).begin(), (x).end()
#define pb push_back
#define ins insert
//STRING ANS: ABXYY
/*
int press(string s){
cerr << "? " << s << "\n";
int x;
cin >> x;
return x;
}*/
//ABXY
string guess_sequence(int n){
string s = "";
array<string, 3> cand;
if(press("AB")){
if(press("A")){
s.pb('A');
cand[0] = 'B';
cand[1] = 'X';
cand[2] = 'Y';
}
else{
s.pb('B');
cand[0] = 'A';
cand[1] = 'X';
cand[2] = 'Y';
}
}
else{
if(press("X")){
s.pb('X');
cand[0] = 'A';
cand[1] = 'B';
cand[2] = 'Y';
}
else{
s.pb('Y');
cand[0] = 'A';
cand[1] = 'B';
cand[2] = 'X';
}
}
//total cost: 2 + n - 2 + 2 = n + 2 WOAHHH!!
while(s.size() != n){
string ask = s + cand[0] + cand[1] +
s + cand[0] + cand[2] +
s + cand[1] + cand[0];
if(s.size() + 1 == n){
//cost 2 op
if(press(s + cand[0]) != s.size()) s += cand[0];
else if(press(s + cand[1]) != s.size()) s += cand[1];
else s += cand[2];
return s;
}
int match = press(ask);
if(match == s.size()) s.pb('Y');
else if(match == s.size() + 1){
//now we only have 2 left, cand[0] and cand[1]
//how to find?
//ask [s]cand[1]cand[1]
//let sz be the old s
// if match = s.size() -> cand[1] cannot be s[sz + 1]
// then s[sz + 1] is cand[0]
// [s]cand[0]
// but if [s]cand[0][cand[1, 2] is nxt then match = sz + 2
// so it must be [s]cand[0]cand[0]
string ask2 = s + cand[1] + cand[1];
int match2 = press(ask2);
if(match2 == s.size()){
s += cand[0] + cand[0];
}
//now 1 character match
// [s]cand[1]
// cannot be [s]cand[1]cand[1]
// so it's cand[0] or cand[2]
// can't be cand[0], if so then match = 2
//-> [s]cand[0]cand[2]
else if(match2 + 1 == s.size()){
s += cand[0] + cand[2];
}
else s += cand[1] + cand[1];
}
else if(match == s.size() + 2){
string ask2 = s + cand[0] + cand[1];
int match2 = press(ask2);
if(match2 == s.size()) s += cand[0] + cand[2];
else s += cand[0] + cand[1];
}
}
return s;
}
///---------MAIN TESTING SOLUTION----------///
///-----------ERASE WHEN SUBMIT-----------///
/*
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << guess_sequence(4);
return 0;
}
*/