This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#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();
| ^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |