Submission #1248566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248566		antonn	Combo (IOI18_combo)	C++20	0 / 100	19 ms	408 KiB

combo

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

using namespace std;

typedef long long ll;

/*
string hidden;

int press(string s) {
    set<string> st;
    for (int i = 0; i < s.size(); ++i) {
        string sub = "";
        for (int j = i; j < s.size(); ++j) {
            sub += s[j];
            st.insert(sub);
        }
    }
    int ans = 0;
    for (int i = 1; i <= hidden.size(); ++i) {
        string pref = "";
        for (int j = 0; j < i; ++j) pref += hidden[j];
        if (st.find(pref) != st.end()) ans = i;
    }
    return ans;
}
*/
int ask(int n, string s, char c) {
    string query = s;
    for (int i = 1; i <= n; ++i) query += c;
    return press(query);
}

string guess_sequence(int n) {
    string s = "";
    if (press("A") == 1) s += "A";
    else if (press("B") == 1) s += "B";
    else if (press("X") == 1) s += "X";
    else s += "Y";
    
    if (n == 1) return s;
    
    vector<char> c;
    for (auto ch : {'A', 'B', 'X', 'Y'}) {
        if (ch != s[0]) {
            c.push_back(ch);
        }
    }
    
    while (s.size() < n) {
        vector<char> c;
        for (auto ch : {'A', 'B', 'X', 'Y'}) {
            if (ch != s[0] && ch != s.back()) {
                c.push_back(ch);
            }
        }
        int len = s.size();
        int x = ask(n, s, c[0]);
        if (x != len) {
            for (int j = 1; j <= x - len; ++j) s += c[0];
        } else {
            x = ask(n, s, c[1]);
            for (int j = 1; j <= x - len; ++j) s += c[1];
        }
    }
    return s;
}

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