Submission #204457

#	Time	Username	Problem	Language	Result	Execution time	Memory
204457		bogdan_ogorodniy	Combo (IOI18_combo)	C++14	10 / 100	98 ms	700 KiB

combo

#include <bits/stdc++.h>
#include "combo.h"
using namespace std;
// string need;
// int press(string p) {
//     string s = need + "#" + p;
//     int n = (int) s.length();
//     vector<int> pi (n);
//     for (int i = 1; i < n; ++i) {
//         int j = pi[i - 1];
//         while (j > 0 && s[i] != s[j])
//             j = pi[j - 1];
//         if (s[i] == s[j]) ++j;
//         pi[i] = j;
//     }
//     int ans = 0;
//     for (int i = need.size(); i < s.size(); i++) {
//         ans = max(ans, pi[i]);
//     }  
//     cout << s << '\t' << ans << '\n';
//     return ans;
// }

string make_to(string s, int n) {
    for (int i = s.size(); i <= n; i++) {
        s.push_back(s[0]);
    }
    return s;
}

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

string guess_sequence(int n) {
    string ans;
    for (int i = 0; i < n; i++) {
        int best = 0;
        string nans;
        random_shuffle(ch.begin(), ch.end());
        for (auto it : ch) {
            string tmp = ans;
            if (i && it == ans[0]) continue;
            tmp.push_back(it);
            int resp = press(make_to(tmp, n + 2));
            if (resp > best) {
                best = resp;
                nans = tmp;
            }
            if (best == i + 1) break;
        }
        ans = nans;
    }
    return ans;
}

// signed main() {
//     cin >> need;
//     cout << guess_sequence(need.size());


//     return 0;
// } 

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