Submission #839614

#	Time	Username	Problem	Language	Result	Execution time	Memory
839614		sleepntsheep	Combo (IOI18_combo)	C++17	10 / 100	37 ms	440 KiB

combo

#include "combo.h"
#include <string>
#include <vector>
using namespace std;

#define BUT "ABXY"

string guess_sequence(int N)
{
    string ans;
    int j = 0;
    vector<int> non(2005, 0);

    for (int i = 0; i < 4; ++i)
    {
        if (i == 3)
            ans[0] = 'Y', ++j;
        else
        {
            ans.resize(2);
            ans[0] = BUT[i];
            ans[1] = 'A';
            int k = press(ans);
            if (k == 1) ++j, non[1] |= 1;
            if (k == 2) j += 2;
            if (k >= 1) break;
        }
    }

    for (int i = j; i < N - 1;)
    {
        int nxt = i + 1;
        for (int j = 0; j < 4; j++)
        {
            if (j == 3)
                ans[i++] = 'Y';
            else
            {
                if (non[i] & (1 << j)) continue;
                ans.resize(i+2);
                ans[i] = BUT[j];
                ans[i+1] = 'A';
                int k = press(ans);
                if (k == i + 1) non[i+1] |= 1;
                if (k == i + 2) { nxt = i + 2; ans[i+1] = 'A'; }
                if (k >= i + 1) break;
            }
        }
        i = nxt;
    }

    ans.resize(N);
    for (int j = 0; j < 4; j++)
    {
        if (j == 3)
            ans[N-1] = 'Y';
        else
        {
            if (non[N-1] & (1 << j)) continue;
            ans[N-1] = BUT[j];
            int k = press(ans);
            if (k == N) break;
        }
    }

    return ans;
}

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