Submission #1305162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305162		kaloyan	Combo (IOI18_combo)	C++20	0 / 100	1 ms	332 KiB

combo

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cassert>

using namespace std;

int press(string p);

void fill(string &str, int l, int r, char c)
{
    for(int i = l ; i <= r ; ++i)
    {
        str[i] = c;
    }
}

void init(string &str, char c, int size)
{
    str.resize(size);

    for(int i = 0 ; i < size ; ++i)
    {
        str[i] = c;
    }
}

string guess_sequence(int N)
{
    string str, res;
    init(res, '0', N);

    char head = '0';
    for(char symbol : {'A', 'B', 'X'})
    {
        init(str, symbol, N);
        
        if(press(str) == 1)
        {
            head = symbol;
            break;
        }
    }

    if(head == '0')
    {
        head = 'Y';
    }

    std::vector<char> next;
    
    for(char symbol : {'A', 'B', 'X', 'Y'})
    {
        if(symbol == head)
        {
            continue;
        }

        next.push_back(symbol);
    }

    res[0] = head;
    for(int i = 1 ; i < N - 1 ; ++i)
    {
        init(str, '0', 4 * N);
        
        for(int ptr = 0 ; ptr < 4 * N ; ptr += N)
        {
            for(int j = 0 ; j <= i - 1 ; ++j)
            {
                str[ptr + j] = res[j];
            }

            if(ptr == 0)
            {
                str[ptr + i] = next[0];
                fill(str, ptr + i + 1, ptr + N - 1, head);
            }
            else if(ptr == N)
            {
                str[ptr + i] = next[1];
                str[ptr + i + 1] = next[0];
                fill(str, ptr + i + 2, ptr + N - 1, head);
            }
            else if(ptr == 2 * N)
            {
                str[ptr + i] = next[1];
                str[ptr + i + 1] = next[1];
                fill(str, ptr + i + 2, ptr + N - 1, head);
            }
            else
            {
                str[ptr + i] = next[1];
                str[ptr + i + 1] = next[2];
                fill(str, ptr + i + 2, ptr + N - 1, head);
            }
        }

        int res_size = i - 1;
        int prefix_size = press(str);

        if(prefix_size == res_size + 1)
        {   
            res[i] = next[0];
        }
        else if(prefix_size == res_size + 2)
        {
            res[i] = next[1];
        }
        else
        {
            assert(prefix_size == res_size);
            res[i] = next[2];
        }
    }

    char tail = '0';
    for(char symbol : next)
    {
        init(str, '0', N);

        for(int i = 0 ; i < N - 1 ; ++i)
        {
            str[i] = res[i];
        }

        str[N - 1] = symbol;
        
        if(press(str) == N)
        {
            tail = symbol;
            break;
        }
    }

    if(tail == '0')
    {
        tail = next.back();
    }

    res[N - 1] = tail;
    return res;
}

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