Submission #777464

#	Time	Username	Problem	Language	Result	Execution time	Memory
777464		dxz05	Mađioničar (COI22_madionicar)	C++17	25 / 100	804 ms	2760 KiB

Main

//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 1e5 + 3e2;

int queries;
string hidden_string;

int ask(int l, int r){
    queries++;

    if (!hidden_string.empty()){
        string t = hidden_string.substr(l, r - l + 1);
        string rt = string(rall(t));
        return t == rt;
    }

    cout << "? " << l + 1 << ' ' << r + 1 << endl;
    int res;
    cin >> res;
    return res;
}

int find_palindrome(const string &s){
    int n = (int) s.size();

    ll p = 7;
    vector<ll> pw(n);
    pw[0] = 1;
    for (int i = 1; i < n; i++) pw[i] = pw[i - 1] * p % MOD;

    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++){
        a[i] = s[i] % MOD;
        if (i > 0) a[i] += a[i - 1] * p;
        a[i] %= MOD;
    }
    for (int i = n - 1; i >= 0; i--){
        b[i] = s[i] % MOD;
        if (i + 1 < n) b[i] += b[i + 1] * p;
        b[i] %= MOD;
    }

    auto check = [&](int len) -> bool{
        int i = 0, j = len - 1, h = (len + 1) / 2;
        for (; j < n; i++, j++){
            int m1 = i + h - 1;
            int m2 = j - h + 1;

            ll x = a[m1], y = b[m2];
            if (i > 0) x -= a[i - 1] * pw[h];
            if (j + 1 < n) y -= b[j + 1] * pw[h];

            x %= MOD, y %= MOD;
            if (x < 0) x += MOD;
            if (y < 0) y += MOD;

            if (x == y) return true;
        }

        return false;
    };

    int ans = 0;

    int l, r;
    l = 1, r = (n + 1) / 2;
    while (l <= r){
        int m = (l + r) >> 1;
        if (check(2 * m - 1)){
            ans = max(ans, 2 * m - 1);
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    l = 1, r = n / 2;
    while (l <= r){
        int m = (l + r) >> 1;
        if (check(2 * m)){
            ans = max(ans, 2 * m);
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    return ans;
}

void solve(){
//    hidden_string = "aabababbbbaaababa";

    int n;
    if (hidden_string.empty()){
        cin >> n;
    } else {
        n = (int) hidden_string.size();
    }

    string s(n, '?');
    s[0] = 'a';
    for (int i = 0; i + 1 < n; i++){
        if (ask(i, i + 1)){
            s[i + 1] = s[i];
        } else {
            s[i + 1] = (s[i] == 'a' ? 'b' : 'a');
        }
    }

    cout << "! " << find_palindrome(s) << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:132:13: warning: unused variable 'startTime' [-Wunused-variable]
  132 |     clock_t startTime = clock();
      |             ^~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 37