Submission #1162902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162902		InvMOD	Combo (IOI18_combo)	C++20	100 / 100	8 ms	520 KiB

combo

#include<bits/stdc++.h>

//#define name "InvMOD"
#ifndef name
    #include "combo.h"
#endif // name

using namespace std;

string guess_sequence(int n){
    string answer = "";

    // find first candidate

    vector<string> candidate = {"A", "B", "X", "Y"};
    auto del_first_can = [&](string x) -> void{
        for(int i = 0; i < 4; i++){
            if(candidate[i] == x){
                answer += x;
                candidate.erase(candidate.begin() + i);
                break;
            }
        }
    };

    if(press("AB")){
        if(press("A")){
            del_first_can("A");
        }
        else del_first_can("B");
    }
    else if(press("X")) del_first_can("X");
    else del_first_can("Y");

    //cout << "CANDIDATE: " << candidate[0] <<" " << candidate[1] <<" " << candidate[2] << "\n";
    for(int i = 1; i < n - 1; i++){
        // 4 * (n - 2) + 2 * 3 + 1 < 4 * n
        string ask = answer + candidate[0] +
                     answer + (candidate[1] + candidate[2]) +
                     answer + (candidate[1] + candidate[0]) +
                     answer + (candidate[1] + candidate[1]);
        assert((int) ask.size() < 4 * n);
        int val = press(ask);
        if(val == i){
            answer = answer + candidate[2];
        }
        else if(val == i + 1){
            answer = answer + candidate[0];
        }
        else{
            answer = answer + candidate[1];
        }
        //cout << "AFTER ASK: " << i <<" " << answer << "\n";
    }

    if(n > 1){
        if(press(answer + candidate[0]) == n){
            answer = answer + candidate[0];
        }
        else if(press(answer + candidate[1]) == n){
            answer = answer + candidate[1];
        }
        else answer = answer + candidate[2];
    }

    // total operation = (n - 2) + 2 * 2
    return answer;
}

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