Submission #1289432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289432		andreim	Combo (IOI18_combo)	C++20	5 / 100	1082 ms	1188 KiB

combo

#include "combo.h"
#include <random>
#include <unordered_map>
using namespace std;

// 0 : A, 1 : B, 2 : X, 3 : Y

mt19937 rng(42);

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

bool aucuneCorrelation(string a, vector<unordered_map<char, bool>>& b, int N, int vraiN)
{
    for (int i = 0; i < 1 && i < (int)a.length(); i++)
    {
        if (b[vraiN - N + i][a[i]])
            return false;
    }
    return true;
}

string genRandom(int vraiN, int N, string old, vector<unordered_map<char, bool>>& vus, vector<unordered_map<char, bool>>& vusDuDernier)
{
    string S = "";
    do
    {
        S = "";
        for (int i = 0; i < N; i++)
            S += toBoutons[uniform_int_distribution<int>(0, 3)(rng)];
    } while (!aucuneCorrelation(S, vus, N, vraiN));

    for (int i = 0; i < (int)S.length(); i++)
        vus[vraiN - N + i][S[i]] = true;
    for (int i = 0; i < (int)S.length(); i++)
        vusDuDernier[vraiN - N + i][S[i]] = true;

    return S;
}

string extractGood(int N, string S)
{
    string res;
    for (int i = 0; i < N; i++)
        res += S[i];
    
    return res;
}

string guess_sequence(int N)
{
    int coinsPrec = 0;
    int coinsPrecPrec = 0;
    string p = "";

    vector<unordered_map<char, bool>> vus(N);
    while (coinsPrec < N)
    {
        vector<unordered_map<char, bool>> vusDuDernier(N);
        coinsPrecPrec = coinsPrec;
        p = extractGood(coinsPrec, p) + genRandom(N, N - coinsPrec, p, vus, vusDuDernier);
        coinsPrec = press(p);
        if (coinsPrec > coinsPrecPrec)
        {
            for (int i = coinsPrec; i < N; i++)
                vus[i] = vusDuDernier[i];
        }
    }
    
    return p;
}

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