Submission #580771

#	Time	Username	Problem	Language	Result	Execution time	Memory
580771		definitelynotmee	Combo (IOI18_combo)	C++17	100 / 100	35 ms	552 KiB

combo

#include "combo.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

std::string guess_sequence(int N) {
    string resp;
    vector<char> poss = {'A', 'B', 'X', 'Y'};
    int ini = 0, fim = 3;
    while(ini!=fim){
        int m = (ini+fim)>>1;
        string guess;
        for(int i = ini; i <= m; i++){
            guess.push_back(poss[i]);
        }
        if(press(guess))
            fim = m;
        else ini = m+1;
    }
    resp.push_back(poss[ini]);
    if(N == 1)
        return resp;
        
    poss.erase(poss.begin()+ini);

    for(int i = 1; i < N-1; i++){
        string guess;
        resp.push_back(poss[1]);

        guess.append(resp);
        resp.pop_back();
        resp.push_back(poss[2]);
        for(int j = 0; j < 3; j++){
            resp.push_back(poss[j]);
            guess.append(resp);
            resp.pop_back();
        }
        resp.pop_back();
        int ret = press(guess);
        resp+=poss[ret-resp.size()];
    }
    ini = 0, fim = 2;
    while(ini!=fim){
        int m = (ini+fim)>>1;
        string guess;
        for(int i = ini; i <= m; i++){
            guess.append(resp);
            guess.push_back(poss[i]);
        }
        if(press(guess)-resp.size())
            fim = m;
        else ini = m+1;
    }
    resp.push_back(poss[ini]);

    return resp;
}

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