Submission #959978

#	Time	Username	Problem	Language	Result	Execution time	Memory
959978		pcc	Mađioničar (COI22_madionicar)	C++17	100 / 100	1369 ms	14848 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];
map<pii,int> mp;

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;
	l = (l+1)>>1;
	r = (r+1)>>1;
	if(mp.find(pii(l,r)) != mp.end())return mp[pii(l,r)];
	cout<<"? "<<l<<' '<<r<<endl;
	/*
	cerr<<"? "<<l<<' '<<r<<endl;
   */
	int re;
	cin>>re;
	return mp[pii(l,r)] = 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;
}

Compilation message (stderr)

Main.cpp: In function 'bool check(int, int)':
Main.cpp:32:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   32 |  return mp[pii(l,r)] = re;

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