oj.uz

Submission #777464

# Submission time Handle Problem Language Result Execution time Memory
777464 2023-07-09T09:18:48 Z dxz05 Mađioničar (COI22_madionicar) C++17
25 / 100
 804 ms 2760 KB 
//#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 456 KB Output is correct
2 Incorrect 32 ms 440 KB L = 207, expected 7
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 456 KB Output is correct
2 Incorrect 32 ms 440 KB L = 207, expected 7
3 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 2696 KB Output is correct
2 Correct 699 ms 2696 KB Output is correct
3 Correct 525 ms 2720 KB Output is correct
4 Correct 744 ms 2760 KB Output is correct
5 Correct 804 ms 2696 KB Output is correct
6 Correct 505 ms 2696 KB Output is correct
7 Correct 731 ms 2760 KB Output is correct
8 Correct 600 ms 2700 KB Output is correct
9 Correct 780 ms 2704 KB Output is correct
10 Correct 713 ms 2696 KB Output is correct
11 Correct 680 ms 2708 KB Output is correct
12 Correct 780 ms 2700 KB Output is correct
13 Correct 722 ms 2696 KB Output is correct
14 Correct 647 ms 2700 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 456 KB Output is correct
2 Incorrect 32 ms 440 KB L = 207, expected 7
3 Halted 0 ms 0 KB -