Submission #305047

#	Time	Username	Problem	Language	Result	Execution time	Memory
305047		mihai145	Combo (IOI18_combo)	C++14	100 / 100	47 ms	652 KiB

combo

#include "combo.h"
#include <vector>
#include <set>
#include <cassert>

std::string guess_sequence(int N)
{
    std::string s1 = "", s2 = "", s3 = "";

    ///first letter logic
    int coins = press("AB");
    if(coins == 0)
    {
        ///first letter is X or Y
        coins = press("X");
        if(coins == 0)
            s1 += 'Y';
        else
            s1 += 'X';
    }
    else
    {
        ///first letter is A or B
        coins = press("A");
        if(coins == 0)
            s1 += 'B';
        else
            s1 += 'A';
    }

    std::set <char> opts;
    opts.insert('A');
    opts.insert('B');
    opts.insert('X');
    opts.insert('Y');
    opts.erase(s1[0]);

    std::vector <char> optv;
    for(auto it : opts)
        optv.push_back(it);

    while(true)
    {
        ///EDGE CASES
        if(s2 == "" && s3 == "")
        {
            if((int)s1.size() == N)
                break;

            ///s1 is for sure a correct preffix
            if((int)s1.size() == N - 1)
            {
                coins = press(s1 + optv[0] +
                                s1 + optv[1]);

                if(coins == (int)s1.size() + 1)
                {
                    coins = press(s1 + optv[0]);

                    if(coins == (int)s1.size() + 1)
                        s1 += optv[0];
                    else
                        s1 += optv[1];
                }
                else
                {
                    s1 += optv[2];
                }

                break;
            }
        }
        else
        {
            ///one of s1, s2 and s3 is a correct preffix
            if((int)s1.size() == N)
            {
                coins = press(s1 + s2);

                if(coins == N)
                {
                    coins = press(s1);
                    if(coins != N)
                        s1 = s2;
                }
                else
                    s1 = s3;

                break;
            }
        }

        ///BULK CASES
        if(s2 == "" && s3 == "")
        {
            ///s1 is for sure a correct preffix
            coins = press(s1 + optv[0] + optv[0] +
                            s1 + optv[0] + optv[1] +
                            s1 + optv[0] + optv[2] +
                            s1 + optv[1]);

            if(coins == (int)s1.size() + 2)
            {
                s2 = s1 + optv[0] + optv[1];
                s3 = s1 + optv[0] + optv[2];
                s1 = s1 + optv[0] + optv[0];
            }
            else if(coins == (int)s1.size() + 1)
                s1 += optv[1];
            else
                s1 += optv[2];
        }
        else
        {
            ///one of s1, s2 and s3 is a correct preffix
            coins = press(s1 + optv[0] +
                            s1 + optv[1] +
                            s1 + optv[2] +
                            s2);

            if(coins == (int)s1.size() + 1)
            {
                s2 = s1 + optv[1];
                s3 = s1 + optv[2];
                s1 = s1 + optv[0];
            }
            else if(coins == (int)s1.size())
            {
                s1 = s2;
                s2 = "";
                s3 = "";
            }
            else
            {
                s1 = s3;
                s2 = "";
                s3 = "";
            }
        }
    }

    return s1;
}

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