Submission #1016880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016880		ProtonDecay314	Combo (IOI18_combo)	C++17	100 / 100	26 ms	1832 KiB

combo

/* AM+DG */

/*
AB
A or X, depending on the last query's result

2 queries to get letter 1

Then N - 2 queries for everything except the last letter

Then 2 queries for the last letter

AZXAZYBAZYXAZYY
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
#include "combo.h"

// #define DEBUG

string guess_sequence(int N) {
    string ans;
    
    char first;

    if(press("AB") > 0) {
        if(press("A") > 0) first = 'A';
        else first = 'B';
    } else {
        if(press("X") > 0) first = 'X';
        else first = 'Y';
    }

    ans.pb(first);

    if(N == 1) return ans;

    string poss = "ABXY";

    string nf;

    LI(i, 0, 4) {
        if(poss[i] == first) continue;
        nf.pb(poss[i]);
    }

    LI(i, 0, N - 2) {
        stringstream guess;
        guess << ans;
        guess << nf[1];
        guess << ans;
        guess << nf[2] << nf[0];
        guess << ans;
        guess << nf[2] << nf[1];
        guess << ans;
        guess << nf[2] << nf[2];

        int guess_ans = press(guess.str());

        ans.pb(nf[guess_ans - ((int)ans.size())]);
    }

    // Last letter

    if(press(ans + "A" + ans + "B") == N) {
        if(press(ans + "A") == N) ans.pb('A');
        else ans.pb('B');
    } else {
        if(press(ans + "X") == N) ans.pb('X');
        else ans.pb('Y');
    }

    return ans;
}

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