Submission #154436

#	Time	Username	Problem	Language	Result	Execution time	Memory
154436		andreiomd	Combo (IOI18_combo)	C++11	97 / 100	40 ms	572 KiB

combo

#include "combo.h"
#include <bits/stdc++.h>

using namespace std;

string guess_sequence (int N)
{
    string S;

    char V[4] = {'A', 'B', 'X', 'Y'};

    vector < int > A;

    if(N == 3)
    {
        for(int i = 1; i <= N; ++i)
        {
            if(i == 1)
            {
                int Ret = 0;

                for(int j = 0; j < 3; ++j)
                {
                    S.push_back(V[j]);

                    if(press(S) == i)
                    {
                        Ret = j;

                        break;
                    }
                    else
                        S.pop_back();
                }

                if(S.empty())
                {
                    S.push_back(V[3]);

                    Ret = 3;
                }

                for(int j = 0; j < 4; ++j)
                    if(j != Ret)
                        A.push_back(j);
            }
            else
            {
                for(int j = 0; j < 2; ++j)
                {
                    S.push_back(V[A[j]]);

                    if(press(S) == i)
                        break;
                    else
                        S.pop_back();
                }

                if((int)S.size() != i)
                    S.push_back(V[A[2]]);
            }
        }
    }
    else
    {
        int First = 3;

        bool Ok = false;

        for(int i = 0; i < 3; ++i)
        {
            S.push_back(V[i]);

            if(press(S))
            {
                Ok = true;

                First = i;

                break;
            }
            else
                S.pop_back();
        }

        if(Ok == false)
        {
            Ok = true;

            S.push_back(V[3]);
        }

        if(N == 1)
            return S;

        for(int i = 2; i < N; ++i)
        {
            if(First == 0)
            {
                int X = press(S + "B" + S + "XB" + S + "XX" + S + "XY");

                if(X == (int)S.size() + 1)
                    S.push_back('B');
                else if(X == (int)S.size())
                    S.push_back('Y');
                else
                    S.push_back('X');

                continue;
            }

            if(First == 1)
            {
                int X = press(S + "A" + S + "XA" + S + "XX" + S + "XY");

                if(X == (int)S.size() + 1)
                    S.push_back('A');
                else if(X == (int)S.size())
                    S.push_back('Y');
                else
                    S.push_back('X');

                continue;
            }

            if(First == 2)
            {
                int X = press(S + "A" + S + "BA" + S + "BB" + S + "BY");

                if(X == (int)S.size() + 1)
                    S.push_back('A');
                else if(X == (int)S.size())
                    S.push_back('Y');
                else
                    S.push_back('B');

                continue;
            }

            int X = press(S + "A" + S + "XA" + S + "XB" + S + "XX");

            if(X == (int)S.size() + 1)
                S.push_back('A');
            else if(X == (int)S.size())
                S.push_back('B');
            else
                S.push_back('X');
        }

        for(int i = 0; i < 4; ++i)
            if(i != First)
                A.push_back(i);

        for(int i = 0; i < 2; ++i)
        {
            S.push_back(V[A[i]]);

            if(press(S) == N)
                break;
            else S.pop_back();
        }

        if((int)S.size() != N)
            S.push_back(V[A[2]]);
    }

    return S;
}

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