Submission #439430

#	Time	Username	Problem	Language	Result	Execution time	Memory
439430		DecapitatedO	Combo (IOI18_combo)	C++17	100 / 100	45 ms	620 KiB

combo

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

using namespace std;

vector<char> letters = {'A', 'B', 'X', 'Y'};

string guess_sequence(int N) {
    string p = "";
    int coins;

    if (N == 1) {
        for (int i = 0; i < (int) letters.size() - 1; i++) {
            if ((coins = press(p + letters[i])) > 0) {
                p += letters[i];
                break;
            }
        }
        if ((int) p.size() == 0) {
            p += letters[letters.size() - 1];
        }
        return p;
    }


    // Find first character
    coins = press("AB");
    if (coins > 0) {
        if ((coins = press("A")) > 0) {
            p += 'A';
            letters.erase(letters.begin() + 0);
        }
        else {
            p += 'B';
            letters.erase(letters.begin() + 1);
        }
    }
    else {
        if ((coins = press("X")) > 0) {
            p += 'X';
            letters.erase(letters.begin() + 2);
        }
        else {
            p += 'Y';
            letters.erase(letters.begin() + 3);
        }
    }

    // Find characters 2...N-1
    string guess;
    for (int i = 2; i <= N - 1; i++) {
        guess = p + letters[0] + p + letters[1] + letters[0] + p + letters[1] + letters[1] + p + letters[1] + letters[2];
        coins = press(guess) - p.size();
        switch (coins) {
            case 0:
                p += letters[2];
                break;
            case 1:
                p += letters[0];
                break;
            case 2:
                p += letters[1];
                break;
        }
    }

    // Find last character
    for (int i = 0; i < (int) letters.size() - 1; i++) {
        if ((coins = press(p + letters[i])) == N) {
            p += letters[i];
            letters.erase(letters.begin() + i);
            break;
        }
    }
    if ((int) p.size() == N - 1) {
        p += letters[letters.size() - 1];
    }

    string S = p;
    return S;
}

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