Submission #777120

#	Time	Username	Problem	Language	Result	Execution time	Memory
777120		welleyth	Combo (IOI18_combo)	C++17	100 / 100	25 ms	616 KiB

combo

#include "combo.h"

#include <bits/stdc++.h>

using namespace std;

mt19937 rnd(time(nullptr));

std::string guess_sequence(int N){
    string ans = "";
    if(press("AB")){
        if(press("A"))
            ans = "A";
        else
            ans = "B";
    } else {
        if(press("X"))
            ans = "X";
        else
            ans = "Y";
    }
    vector<string> order;
    string CH[] = {"A","B","X","Y"};
    for(int i = 0; i < 4; i++){
        if(CH[i] != ans)
            order.push_back(CH[i]);
    }
    assert(order.size() == 3);

    for(int i = 2; i <= N; i++){
        if(4*i + 3 <= 4*N){
            int val = press(ans+order[0]+ans+order[1]+order[0]+ans+order[1]+order[1]+ans+order[1]+order[2]);
            if(val == i+1){
                ans += order[1];
            } else if(val == i)
                ans += order[0];
            else
                ans += order[2];
            continue;
        }
        shuffle(order.begin(),order.end(),rnd);
        if(press(ans + order[0] + ans + order[1]) == i){
            if(press(ans + order[0]) == i)
                ans += order[0];
            else
                ans += order[1];
        } else
            ans += order[2];
        /// AB
        /// AC
        /// AA
        /// A B CA CB CC
        /// 5i + 3
        /// AA AB AC B
    }

    return ans;
}
/// sz

/// 3^n < 4n

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