Submission #131778

#	Time	Username	Problem	Language	Result	Execution time	Memory
131778		stoyan_malinin	Combo (IOI18_combo)	C++14	30 / 100	96 ms	408 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'};

bool sure[MAXN];

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();
    bool unknown = false;

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

        if(index==N-1)
        {
            if(unknown==false)
            {
                vector <char> v = allExcept(curr[index]);
                if(askCustom3(v[0])==n) curr[index] = v[0];
                else curr[index] = v[1];
            }
            else
            {
                int res1 = askCustom3(curr[index]);
                if(res1==n)
                {
                    break;
                }
                else
                {
                    unknown = false;
                    continue;
                }
            }

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

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

        if(rnd()%2==0)
        {
            swap(v1[0], v1[1]);
        }
        if(rnd()%2==0)
        {
            swap(v2[0], v2[1]);
        }

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

                unknown = false;
            }
            else
            {
                curr[index] = v1[1];

                unknown = true;
                index++;
            }
        }
        else
        {
            int res1 = askCustom2(index, v1[0], v1[1], curr[index+1]);
            if(res1==index)
            {
                index++;
                unknown = true;
            }
            else
            {
                int res2 = askCustom1(index, v1[0], curr[index+1]);

                if(res2>=index+1) curr[index] = v1[0];
                else curr[index] = v1[1];

                unknown = false;
                index = res1;
            }
        }

        //system("PAUSE");
    }

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

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

Compilation message (stderr)

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

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