Submission #959976

#	Time	Username	Problem	Language	Result	Execution time	Memory
959976		pcc	Mađioničar (COI22_madionicar)	C++17	38 / 100	1164 ms	2540 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long

const int mxn = 2e5+10;
int N;
int Z[mxn];

bool check(int l,int r){
	assert((r-l)%2==0);
	if(l<=0||r>=N*2)return false;
	assert(l<=r);
	if(l%2==0)l++,r--;
	if(r<=l)return true;
	cout<<"? "<<(l+1)/2<<' '<<(r+1)/2<<endl;
	/*
	cerr<<"? "<<l<<' '<<r<<endl;
   */
	int re;
	cin>>re;
	return re;
}

int main(){
	cin>>N;
	int cen = 1,rp = 2;
	Z[1] = 1;
	for(int i = 2;i<N*2;i++){
		//cerr<<i<<":"<<cen<<','<<rp<<endl;
		if(i>=rp);
		else if(Z[cen*2-i]+i<rp){
			Z[i] = Z[cen*2-i];
			continue;
		}
		else if(Z[cen*2-i]+i>rp){
			Z[i] = rp-i;
			continue;
		}
		cen = i,rp = max(i+1,rp);
		while(check(cen*2-rp,rp))rp++;
		Z[i] = rp-i;
		//cerr<<i<<"::"<<Z[i]<<endl;
	}
	//for(int i = 1;i<N*2;i++)cerr<<Z[i]<<' ';cerr<<endl;
	int ans = 0;
	for(int i = 1;i<N*2;i++){
		if(i&1)ans = max(ans,(Z[i]+1)/2*2-1);
		else{
			ans = max(ans,Z[i]-(Z[i]&1));
		}
	}
	cout<<"! "<<ans<<endl;
}

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