Submission #204472

#	Time	Username	Problem	Language	Result	Execution time	Memory
204472		bogdan_ogorodniy	Combo (IOI18_combo)	C++14	100 / 100	61 ms	1508 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 str(char x, char y) {
    string tmp;
    tmp.push_back(x);
    tmp.push_back(y);
    return tmp;
}

string guess_sequence(int n) {
    string ans;
    for (int i = 0; i < n; i++) {
        int best = 0;
        string nans;
        vector <char> cc;
        for (auto it : ch) {
            if (i&&it==ans[0]) continue;
            cc.push_back(it);
        }
        if (cc.size() == 3 && i != n - 1) {
            int resp = press(ans + cc[1] + cc[2] 
                + ans + cc[1] + cc[1] 
                + ans + cc[1] + cc[0]
                + ans + cc[0]);
            if (resp == i) ans.push_back(cc[2]);
            else if (resp == i + 1) ans.push_back(cc[0]);
            else ans.push_back(cc[1]);
        }
        else {
            string tmp1 = ans, tmp2 = ans, tmp3 = ans, tmp4 = ans;
            tmp1.push_back(cc[0]);
            tmp2.push_back(cc[1]);
            tmp3.push_back(cc[2]);
            tmp4.push_back(cc[3]);
            int resp = press(make_to(tmp1, n) + make_to(tmp2, n));
            if (resp >= i + 1) {
                resp = press(make_to(tmp1, n));
                if (resp == i + 1) nans = tmp1;
                else nans = tmp2;
            }
            else {
                resp = press(make_to(tmp3, n));
                if (resp == i + 1) nans = tmp3;
                else nans = tmp4;
            }
            ans = nans;
        }
        // cout << ans << '\n';
    }

    return ans;
}

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


//     return 0;
// } 

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:43:13: warning: unused variable 'best' [-Wunused-variable]
   43 |         int best = 0;
      |             ^~~~

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