Submission #131262

#	Time	Username	Problem	Language	Result	Execution time	Memory
131262		stoyan_malinin	Combo (IOI18_combo)	C++14	30 / 100	102 ms	364 KiB

combo

#include<iostream>
#include<random>
#include "combo.h"
//#include "grader.cpp"

using namespace std;

mt19937 rnd(69420);

const int MAXN = 2005;

int n;
char curr[MAXN];
vector <char> allCharacters = {'A', 'B', 'X', 'Y'};

int currAsked = 0;

int askCurr()
{
    currAsked++;

    string ask = "";
    for(int i = 0;i<n;i++)
    {
        ask += curr[i];
    }

    return press(ask);
}

int askCustom1(int index, char c1, char c2)
{
    currAsked++;

    string ask;
    for(int i = 0;i<n;i++)
    {
        if(i!=index && i!=index+1)
        {
            ask += curr[i];
        }
        else
        {
            if(i==index) ask += c1;
            else ask += c2;
        }
    }

    //cout << "ask:" << ask << '\n';
    return press(ask);
}

int askCustom2(int index, char c1_1, char c1_2, char c2)
{
    currAsked++;

    string ask;
    for(int i = 0;i<n;i++)
    {
        if(i!=index && i!=index+1)
        {
            ask += curr[i];
        }
        else
        {
            if(i==index) ask += c1_1;
            else ask += c2;
        }
    }
    for(int i = 0;i<n;i++)
    {
        if(i!=index && i!=index+1)
        {
            ask += curr[i];
        }
        else
        {
            if(i==index) ask += c1_2;
            else ask += c2;
        }
    }

    return press(ask);
}

int askCustom3(char c1)
{
    currAsked++;

    string ask;
    for(int i = 0;i<n-1;i++)
    {
        ask += curr[i];
    }
    ask += c1;

    return press(ask);
}

int askCustom4(int index, char c1, char c2_1, char c2_2)
{
    currAsked++;

    string ask;
    for(int i = 0;i<n;i++)
    {
        if(i!=index && i!=index+1)
        {
            ask += curr[i];
        }
        else
        {
            if(i==index) ask += c1;
            else ask += c2_1;
        }
    }
    for(int i = 0;i<n;i++)
    {
        if(i!=index && i!=index+1)
        {
            ask += curr[i];
        }
        else
        {
            if(i==index) ask += c1;
            else ask += c2_2;
        }
    }

    return press(ask);
}

vector <char> allExcept(char c)
{
    vector <char> output;
    for(char item: allCharacters)
    {
        if(item!=c)
        {
            output.push_back(item);
        }
    }

    return output;
}

string guess_sequence(int N)
{
    n = N;
    srand(69);

    int index = 1;
    string answer = "";

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

    for(int i = 0;i<allCharacters.size();i++)
    {
        if(allCharacters[i]==answer[0])
        {
            allCharacters.erase(allCharacters.begin()+i);
            break;
        }
    }

    curr[0] = answer[0];
    for(int i = 1;i<N;i++)
    {
        curr[i] = allCharacters[rnd()%3];
    }

    index = askCurr();
    while(index<N)
    {
        //cout << index << ":";
        //for(int i = 0;i<n;i++) cout << curr[i];
        //cout << '\n';

        if(index==N-1)
        {
            vector <char> v = allExcept(curr[index]);
            if(askCustom3(v[0])==n) curr[index] = v[0];
            else curr[index] = v[1];

            //cout << "DEEEBA" << '\n';
            break;
        }

        currAsked = 0;

        vector <char> v1 = allExcept(curr[index]);
        vector <char> v2 = allExcept(curr[index+1]);

        int res1 = askCustom1(index, v1[0], curr[index]);
        if(res1>=index+1) curr[index] = v1[0];
        else curr[index] = v1[1];

        int res2 = askCustom4(index, curr[index], v2[0], v2[1]);
        if(res2>=index+2)
        {
            int res3 = askCustom1(index, curr[index], v2[0]);

            if(res3>=index+2) curr[index+1] = v2[0];
            else curr[index+1] = v2[1];

            index = res2;
            //cout << currAsked << " " << index << '\n';

            continue;
        }

        index = askCustom1(index, curr[index], curr[index+1]);
        //cout << currAsked << " " << index << '\n';
    }

    for(int i = 1;i<n;i++) answer += curr[i];

    //cout << answer.size() << '\n';
    return answer;
}
/*
AXXXBBBBBBBBYYYYYYYXXXXXBXBBBBBBXBXBXBXBXBXBXBXBXBXBBXBXBBBXBXBXBBXBXXXYYXYYXXYYXYYXYYXYXYYXYYXYYXYXYXYBYXBYXYBXBXBYYBXYBXBYXBYXBYXYBXYBBYXYBXYBXXBYXYBXBYXYBXYBYBXYBXYBXYBBYXYBXYBYBXYBXYBYBYBXYBXYBXYYBXBYXYBXYBXYBYBXYBYXYBBYXBYXYBYBXYBYBXYBYBXYBYBXYYXYYXYXYYXYYXYXYXYYXYBYXYBXBBYXXBYXBYXYYBXYBYXYBXBBYXYBXBYXBYXYBXBYYBXYBXYBXYBXBXXXXYXYXYYXBXYBXYBXYXBYXBYXBXYBXYXBYXBXBBB
*/

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:166:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     for(int i = 0;i<allCharacters.size();i++)
      |                   ~^~~~~~~~~~~~~~~~~~~~~

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