Submission #1248631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248631		countless	Combo (IOI18_combo)	C++20	100 / 100	8 ms	524 KiB

combo

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"
#define all(x) (x).begin(), (x).end()

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

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

    // find first character in 2 queries
    {
        p = "AB";
        int x = press(p);

        if (x >= 1) {
            p = "A";
            x = press(p);

            p = (x == 1 ? "A" : "B");
        } else {
            p = "X";
            x = press(p);

            p = (x == 1 ? "X" : "Y");
        }

        st.erase(find(all(st), p[0]));
    }

    // find the rest of the characters
    {
        int t = 2;
        for (; t <= N; t++) {
            string q = "";
            q += p + st[1];
            q += p + st[2] + st[0];
            q += p + st[2] + st[1];
            q += p + st[2] + st[2];

            if (q.size() > 4 * N) break;

            int x = press(q);

            if (x == t-1) {
                p += st[0];
            } else if (x == t) {
                p += st[1];
            } else if (x == t+1) {
                p += st[2];
            } else assert(0);
        }

        // t == N
        for (; t <= N; t++) {
            string q;
            for (int i = 0; i < 2; i++) {
                q = (p + st[i]);
                // cerr << q << endl;
                int x = press(q);
                if (x == t) {
                    p = q;
                    break;
                }
            }

            if (p.size() != t) {
                p += st[2];
            }
        }
    }

    // cerr << p << endl;
    return p;
}

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