oj.uz

Submission #959947

# Submission time Handle Problem Language Result Execution time Memory
959947 2024-04-09T11:05:44 Z pcc Mađioničar (COI22_madionicar) C++17
0 / 100
 1030 ms 1760 KB 
#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){
	if(l<=0||r>=N*2)return false;
	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 = i+1;
		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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 1216 KB Output is correct
2 Correct 69 ms 1112 KB Output is correct
3 Correct 70 ms 1224 KB Output is correct
4 Correct 760 ms 936 KB Output is correct
5 Correct 510 ms 984 KB Output is correct
6 Correct 186 ms 980 KB Output is correct
7 Runtime error 1000 ms 424 KB Execution killed with signal 13
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 1216 KB Output is correct
2 Correct 69 ms 1112 KB Output is correct
3 Correct 70 ms 1224 KB Output is correct
4 Correct 760 ms 936 KB Output is correct
5 Correct 510 ms 984 KB Output is correct
6 Correct 186 ms 980 KB Output is correct
7 Runtime error 1000 ms 424 KB Execution killed with signal 13
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1030 ms 1760 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 1216 KB Output is correct
2 Correct 69 ms 1112 KB Output is correct
3 Correct 70 ms 1224 KB Output is correct
4 Correct 760 ms 936 KB Output is correct
5 Correct 510 ms 984 KB Output is correct
6 Correct 186 ms 980 KB Output is correct
7 Runtime error 1000 ms 424 KB Execution killed with signal 13
8 Halted 0 ms 0 KB -