oj.uz

Submission #959954

# Submission time Handle Problem Language Result Execution time Memory
959954 2024-04-09T11:14:12 Z pcc Mađioničar (COI22_madionicar) C++17
0 / 100
 1036 ms 1600 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){
	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 = 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 129 ms 1212 KB Output is correct
2 Correct 70 ms 1468 KB Output is correct
3 Correct 60 ms 1236 KB Output is correct
4 Correct 771 ms 984 KB Output is correct
5 Correct 599 ms 1236 KB Output is correct
6 Correct 166 ms 976 KB Output is correct
7 Runtime error 1036 ms 420 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 129 ms 1212 KB Output is correct
2 Correct 70 ms 1468 KB Output is correct
3 Correct 60 ms 1236 KB Output is correct
4 Correct 771 ms 984 KB Output is correct
5 Correct 599 ms 1236 KB Output is correct
6 Correct 166 ms 976 KB Output is correct
7 Runtime error 1036 ms 420 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 1036 ms 1600 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 129 ms 1212 KB Output is correct
2 Correct 70 ms 1468 KB Output is correct
3 Correct 60 ms 1236 KB Output is correct
4 Correct 771 ms 984 KB Output is correct
5 Correct 599 ms 1236 KB Output is correct
6 Correct 166 ms 976 KB Output is correct
7 Runtime error 1036 ms 420 KB Execution killed with signal 13
8 Halted 0 ms 0 KB -