Submission #131248

#	Time	Username	Problem	Language	Result	Execution time	Memory
131248		stoyan_malinin	Combo (IOI18_combo)	C++14	30 / 100	101 ms	324 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 askCurr()
{
    string ask = "";
    for(int i = 0;i<n;i++)
    {
        ask += curr[i];
    }

    return press(ask);
}

int askCustom1(int index, char c1, char c2)
{
    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)
{
    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)
{
    string ask;
    for(int i = 0;i<n-1;i++)
    {
        ask += curr[i];
    }
    ask += c1;

    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;
        }

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

        int res1 = askCustom2(index, v1[0], v1[1], v2[0]);
        //cout << res1 << '\n';

        if(res1>=index+2) //curr[index+1] = v2[0]
        {
            //cout << "INSIDE 1" << '\n';
            curr[index+1] = v2[0];

            int res2 = askCustom1(index, v1[0], v2[0]);
            if(res2>=index+1)
            {
                curr[index] = v1[0];
            }
            else
            {
                curr[index] = v1[1];
            }

            index = res1;
            continue;
        }
        if(res1==index+1) //curr[index+1] != v2[0]
        {
            //cout << "INSIDE 2" << '\n';

            int res2 = askCustom1(index, v1[0], v2[1]);
            if(res2>=index+1)
            {
                curr[index] = v1[0];
                //cout << "oke " << res2 << '\n';

                if(res2>=index+2) {curr[index+1] = v2[1];}
                else res2 = askCustom1(index, curr[index], curr[index+1]);

                index = res2;
                continue;
            }

            res2 = askCustom1(index, v1[1], v2[1]);
            if(res2>=index+1)
            {
                curr[index] = v1[1];

                if(res2>=index+2) curr[index+1] = v2[1];
                else res2 = askCustom1(index, curr[index], curr[index+1]);

                index = res2;
                continue;
            }
        }

        //system("PAUSE");
    }

    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:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i = 0;i<allCharacters.size();i++)
      |                   ~^~~~~~~~~~~~~~~~~~~~~

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