Submission #374803

#	Time	Username	Problem	Language	Result	Execution time	Memory
374803		Alex_tz307	Combo (IOI18_combo)	C++17	100 / 100	45 ms	568 KiB

combo

#include <bits/stdc++.h>
#include "combo.h"

using namespace std;

string guess_sequence(int N) {
    string sol;
    int ok = press("AB");
    if(ok) {
        int first = press("A");
        if(first)
            sol = "A";
        else
            sol = "B";
    }
    else {
        int first = press("X");
        if(first)
            sol = "X";
        else
            sol = "Y";
    }
    string mask = "";
    for(const char &ch : "ABXY")
        if(ch != sol[0])
            mask += ch;
    if(N == 1)
        return sol;
    for(int i = 2; i < N; ++i) {
        string ask = sol + mask[0] + sol + mask[1] + mask[0] + sol + mask[1] + mask[1] + sol + mask[1] + mask[2];
        /// pentru A pe prima pozitie si BXY mask de exemplu(restul cazurilor se rezolva analog, dar cu alte caractere)
        /// A nu mai poate sa apara in sir, deci ramanem cu B, X, Y
        /// daca urmatorul e B, sol + mask[0] va fi raspunsul(de lungime i) si sigur
        /// nu se obtine lungime mai mare din urmatoarele pentru ca avem X primul caracter adaugat la s
        /// ramanem cu X si Y
        /// fixam X, verificam daca se poate obtine X si daca nu se poate obtine X, atunci obtinem Y
        /// pentru a afla daca X e ok, incercam toate variantele de urmator caracter de dupa X(B, X, Y)
        /// daca avem X ca raspuns corect, atunci lungimea obtinuta este i + 1
        /// nu putem incerca direct pref + X(si sa avem lungime i) pentru ca deja am incercat asta cu B
        /// si daca ni s-ar returna din functia press valoarea i nu am sti daca avem B sau X
        /// cea mai importanta parte a constructiei, este proprietatea speciala a sirului:
        /// A nu mai poate sa apara dupa prima pozitie
        /// astfel, de fiecare data cand adaug la ask s, "resetez" intr-un fel sirul ask, deoarece il adaug pe A ca prim caracter al lui s
        /// defapt, prin asta, combin 4 query-uri de prefixe intr-unul singur
        int lg = press(ask);
        if(lg == i)
            sol += mask[0];
        else
            if(lg == i + 1)
                sol += mask[1];
        else
            sol += mask[2];
    }
    if(press(sol + mask[0]) == N)
        return sol + mask[0];
    if(press(sol + mask[1]) == N)
        return sol + mask[1];
    return sol + mask[2];
}

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