Submission #1274668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274668		raditya_noor	Mađioničar (COI22_madionicar)	C++20	38 / 100	1563 ms	792 KiB

Main

#include <bits/stdc++.h>
#define psb push_back
#define ppb pop_back
#define sz size
#define em empty
#define bgn begin
#define rbgn rbegin
#define fr first
#define sc second
using namespace std;

bool qu(int a, int b){
	cout << "? " << a << ' ' << b << endl;
	bool ret; cin >> ret; return ret;
}

int main(){
	int n; cin >> n;
	int ord[n + 1] = {0}; for(int i = 1; i <= n; i++) ord[i] = i;
	//even lengths
	int ans = 1;
	for(int i = 2, len = 1; i <= n; i++){
		if(qu(i - 1, i)){
			ord[i] = ord[i - 1];
			ans = max(ans, ++len);
		}else len = 1;
	}
	//combine
	for(int i = 2; i <= n; i++){
		if(ord[i - 1] != ord[i]){
			int l = i - 1, r = i;
			while(r + 1 <= n && ord[r] == ord[r + 1]) r++; 
			if(r + 1 <= n) r++;
			bool y = 1;
			while(y){
				while((l - 1 > 0 && r + 1 <= n) && ((ord[l - 1] == ord[l] && ord[r] == ord[r + 1]) || r - l + 1 < ans)){
					l--;
					r++;
				}
				if(l > 0 && r <= n && qu(l, r)){
					ans = max(ans, r - l + 1);
					l--; r++;
				}
				else y = 0;
			}
		}
	}
	cout << "! " << ans << endl;
	return 0;
}

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