Submission #1221695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221695		not_amir	Combo (IOI18_combo)	C++20	100 / 100	8 ms	540 KiB

combo

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

vector<char> C;

int query(string s, array<vector<int>, 3> v) {
    string p = "";
    for (int i = 0; i < 3; i++) {
        p += C[3] + s;
        for (int x : v[i])
            p += C[x];
    }
    return press(p);
}

vector<int> operator+(vector<int> f, vector<int> s) {
    for (int x : s)
        f.push_back(x);
    return f;
}

void pop_front(vector<int> &v) {
    vector<int> nv;
    for (int i = 1; i < v.size(); i++)
        nv.push_back(v[i]);
    v = nv;
}

string guess_sequence(int N) {
    if (press("AB")) {
        if (press("A"))
            C = {'B', 'X', 'Y', 'A'};
        else
            C = {'A', 'X', 'Y', 'B'};
    }
    else {
        if (press("X"))
            C = {'Y', 'B', 'A', 'X'};
        else
            C = {'X', 'B', 'A', 'Y'};
    }
    if (N == 1)
        return string{C[3]};
    if (N == 2) {
        string p = "";
        p += C[3], p += C[0], p += C[3], p += C[1];
        if (press(p) == 1)
            return string{C[3]} + string{C[2]};
        p = string{C[3]} + string{C[0]};
        if (press(p) == 2)
            return p;
        return string{C[3]} + string{C[1]};
    }
    string s = "";
    array<vector<int>, 3> pos = {};
    pos[0] = {0}, pos[1] = {1}, pos[2] = {2};
    for (int i = 0; s.size() + pos[0].size() + 1 < N; i++) {
        int c = query(s, {pos[0] + vector{0}, pos[0] + vector{1}, pos[1] + vector{0}}) - s.size() - pos[0].size();
        if (c <= 0) {
            for (int x : pos[2])
                s.push_back(C[x]);
            pos[0] = {0}, pos[1] = {1}, pos[2] = {2};
        }
        if (c == 1) {
            decltype(pos) tpos;
            tpos[0] = pos[1] + vector{1}, tpos[1] = pos[1] + vector{2}, tpos[2] = pos[0] + vector{2};
            pos = tpos;
        }
        if (c == 2) {
            decltype(pos) tpos;
            tpos[0] = pos[0] + vector{0}, tpos[1] = pos[0] + vector{1}, tpos[2] = pos[1] + vector{0};
            pos = tpos;
        }
        while (!pos[0].empty() && !pos[1].empty() && !pos[2].empty()) {
            if (pos[0][0] == pos[1][0] && pos[1][0] == pos[2][0]) {
                s.push_back(C[pos[0][0]]);
                for (int x : {0, 1, 2})
                    pop_front(pos[x]);
            }
            else
                break;
        }
    }
    string s0, s1, s2;
    s0 = s1 = s2 = C[3] + s;
    for (int x : pos[0])
        s0.push_back(C[x]);
    for (int x : pos[1])
        s1.push_back(C[x]);
    for (int x : pos[2])
        s2.push_back(C[x]);
    if (press(s0) == N)
        return s0;
    if (press(s1) == N)
        return s1;
    return s2;
}

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