Submission #1302762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302762		baodat	Combo (IOI18_combo)	C++20	0 / 100	21 ms	400 KiB

combo

#include <bits/stdc++.h>
#include "combo.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 += cand[2];
        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[1]cand[2]
            else if(match2 + 1 == s.size()){
                s += cand[1] + 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;
}
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95