Submission #83811

#	Time	Username	Problem	Language	Result	Execution time	Memory
83811		AdrienVannson	Combo (IOI18_combo)	C++17	30 / 100	303 ms	444 KiB

combo

#include <bits/stdc++.h>

#include "combo.h"

using namespace std;

const int NB_MAX_CARACTERES = 2000;

string res = "";
bool estPossible[NB_MAX_CARACTERES][3];


string guess_sequence (int nbElements)
{
    srand(42);

    fill(*estPossible, *estPossible+NB_MAX_CARACTERES*3, true);

    if (press("AB") > 0) {
        res += press("A") ? 'A' : 'B';
    }
    else {
        res += press("X") ? 'X' : 'Y';
    }

    if (nbElements == 1) {
        return res;
    }

    string caracteres;
    for (char c : "ABXY") {
        if (c != res[0]) {
            caracteres.push_back(c);
        }
    }

    while ((int)res.size() < nbElements) {

        string requete = res;

        while ((int)requete.size() < nbElements) {

            vector<char> possibles;

            for (int iCaractere=0; iCaractere<3; iCaractere++) {
                if (estPossible[requete.size()][iCaractere]) {
                    possibles.push_back(caracteres[iCaractere]);
                }
            }

            requete += possibles[ rand() % possibles.size() ];
        }

        const int reponse = press(requete);

        while ((int)res.size() < reponse) {
            res += requete[res.size()];
        }

        if ((int)res.size() < nbElements) {
            const int iCaractere = distance(caracteres.begin(), find(caracteres.begin(), caracteres.end(), requete[res.size()]));

            estPossible[res.size()][iCaractere] = false;
        }
    }

    return res;
}

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