Submission #1329707

#TimeUsernameProblemLanguageResultExecution timeMemory
1329707kevinsMađioničar (COI22_madionicar)C++20
25 / 100
250 ms1688 KiB
#include <iostream>
#include <vector>
using namespace std;
#define ll long long

ll longestPalindrome(string s) {
    string T = "#";
    for (char c : s) {
        T += c;
        T += "#";
    }

    int n = T.size();
    vector<int> P(n, 0);

    int C = 0, R = 0;  // center and right boundary
    int maxLen = 0, centerIndex = 0;

    for (int i = 0; i < n; i++) {
        int mirror = 2*C - i;

        if (i < R)
            P[i] = min(R - i, P[mirror]);

        // expand
        while (i - P[i] - 1 >= 0 &&
               i + P[i] + 1 < n &&
               T[i - P[i] - 1] == T[i + P[i] + 1])
        {
            P[i]++;
        }

        // update center and right boundary
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }

        // track max
        if (P[i] > maxLen) {
            maxLen = P[i];
            centerIndex = i;
        }
    }

    return maxLen;
}

int main(){
	ll n;
	cin >> n;

	//since only a and b we just compare letter by letter
	bool letters[n];
	letters[0] = 1;

	for (ll i = 1; i < n; ++i){
		cout << "? " << i << " " << i+1 << "\n";
		cout.flush();
		bool same;
		cin >> same;
		letters[i] = same ? letters[i-1] : !letters[i-1];
	}

	string rec;
	for (ll i = 0; i < n; ++i){
		if (letters[i]) rec.push_back('a');
		else rec.push_back('b');
	}

	cout << "! " << longestPalindrome(rec) << "\n";
	cout.flush();
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...