Submission #1247856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247856		denislav	Combo (IOI18_combo)	C++20	10 / 100	10 ms	460 KiB

combo

# include <iostream>
# include <vector>
# include <algorithm>
# include <random>
using namespace std;
# include "combo.h"
//# include "grader.cpp"

mt19937 rng(1707);

string guess_sequence(int N)
{
    vector<char> letters={'A','B','X','Y'};
    string s;
    int l=0,r=letters.size()-1,lett=0;
    while(l<r)
    {
        int mid=(l+r)/2;
        string guess;
        for(int i=l;i<=mid;i++) guess.push_back(letters[i]);
        if(press(guess))
        {
            r=mid;
            lett=mid;
        }
        else
        {
            l=mid+1;
            lett=mid+1;
        }
    }
    s.push_back(letters[lett]);
    letters.erase(letters.begin()+lett);

    //cout<<"->"<<s<<endl;

    bool shuf=1;
    while((int)s.size()<N)
    {
        if(shuf) shuffle(letters.begin(),letters.end(),rng);
        shuf=0;

        //cout<<letters[0]<<" "<<letters[1]<<" "<<letters[2]<<endl;

        string guess=s;
        guess.push_back(letters[0]);guess.push_back(letters[1]);
        int resp=press(guess);
        if(resp==(int)guess.size())
        {
            s=guess;
            shuf=1;
        }
        else if(resp==(int)s.size()+1)
        {
            s.push_back(letters[0]);
            shuf=1;
        }
        else
        {
            swap(letters[0],letters[1]);
            swap(letters[1],letters[2]);
            shuf=0;
        }

        //cout<<"->"<<s<<endl;
    }

    return s;
}

/*
ABXYY
*/

/*
YXX
*/

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