Submission #703412

#	Time	Username	Problem	Language	Result	Execution time	Memory
703412		SamNguyen	Combo (IOI18_combo)	C++14	97 / 100	33 ms	572 KiB

combo

#include "combo.h"
#include <bits/stdc++.h>
using namespace std;

const string ALPHABET = "ABXY";

namespace SUB1 {
    string guess_sequence(int N) {
        string ans = "";
        for (int i = 0; i < N; i++) {
            for (char c : ALPHABET) {
                ans.push_back(c);
                if (press(ans) == i + 1)
                    break;
                ans.pop_back();
            }
        }

        return ans;
    }
}

namespace SUB2 {
    string guess_sequence(int N) {
        string ans = "";
        for (int i = 0; i < N; i++) {
            int cnt = 0;
            for (auto it = ALPHABET.begin(); it != ALPHABET.end(); it++) {
                char c = *it;
                if (not ans.empty() and c == ans.front())
                    continue;

                cnt++;
                ans.push_back(c);

                if (i == 0 and cnt == 4)
                    break;
                if (i > 0 and cnt == 3)
                    break;

                if (press(ans) == i + 1)
                    break;
                ans.pop_back();
            }
        }

        return ans;
    }
}

namespace SUB3 {
    char commencing_char() {
        for (char c : {'A', 'B', 'X'})
            if (press(string(1, c)) == 1)
                return c;
        return 'Y';
    }

    tuple<string, string, string, string> get_char_roles() {
        char X = commencing_char();
        if (X == 'A')
            return {"A", "B", "X", "Y"};
        if (X == 'B')
            return {"B", "A", "X", "Y"};
        if (X == 'X')
            return {"X", "A", "B", "Y"};
        if (X == 'Y')
            return {"Y", "A", "B", "X"};
        assert(false);
    }

    string guess_sequence(int N) {
        string X, A, B, C;
        tie(X, A, B, C) = get_char_roles();

        string ans = X;
        for (int i = 1; i < N - 1; i++) {
            string P = ans + A + ans + B + A + ans + B + B + ans + B + C;

            int t = press(P);

            if (t == i)
                ans += C;
            if (t == i + 1)
                ans += A;
            if (t == i + 2)
                ans += B;
        }

        if (N > 1) {
            if (press(ans + A) == N)
                ans += A;
            else if (press(ans + B) == N)
                ans += B;
            else
                ans += C;
        }

        return ans;
    }
}

string guess_sequence(int N) {
    if (N == 3)
        return SUB1::guess_sequence(N);

    return SUB3::guess_sequence(N);
}

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