QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#829515#8939. PermutationOIer2008WA 1ms3560kbC++142.2kb2024-12-24 10:36:162024-12-24 10:36:17

Judging History

This is the latest submission verdict.

  • [2024-12-24 10:36:17]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3560kb
  • [2024-12-24 10:36:16]
  • Submitted

answer

#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=l;i<=r;++i)
#define fu(i,l,r) for(int i=l;i<r;++i)
#define fd(i,r,l) for(int i=r;i>=l;--i)
#define ll long long
#define I inline int
#define V inline void
#define B inline bool
#define L inline ll
#define pi pair<int,int>
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vii vector<pi>
#define popc __builtin_popcount
using namespace std;
const int N=1e6+10,mod=998244353;
char St;
I read() {
	int x=0,y=1;char c=getchar();
	while(c<48||c>57) {if(c==45)y=-y;c=getchar();}
	while(c>=48&&c<=57) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*y;
}
L ksm(ll x,int y) {ll t(1);for(;y;y>>=1,x=x*x%mod)if(y&1)t=t*x%mod;return t;}
int s1(0),s2(0);
I ask(int l,int r) {
	if(l==r) return 0;
	cout<<"? "<<l<<" "<<r<<endl;
	s1++;s2+=r-l+1;
	int x;
	cin>>x;return x;
}
I solve(int l,int r) {
	if(l==r) return l;
	int mid=l+r>>1,se=ask(l,r);
	if(se<=mid) {
		if(l==mid) return solve(mid+1,r);
		int se2=ask(l,mid);
		if(se==se2) {//[l,mid]
			r=mid;
			mid=l+r>>1;
			int se3;
			if(se2<=mid) {
				se3=ask(l,mid);
				if(se3==se2) return solve(l,mid);
				else return solve(mid+1,r);
			}
			else {
				se3=ask(mid+1,r);
				if(se3==se2) return solve(mid+1,r);
				else return solve(l,mid);
			}
		}
		else {
			l=mid+1;mid=l+r>>1;
			int se3=ask(se,mid);
			if(se3==se) return solve(l,mid);
			else return solve(mid+1,r);
		}
	}
	else {
		if(mid+1==r) return solve(l,mid);
		int se2=ask(mid+1,r);
		if(se==se2) {
			l=mid+1;
			mid=l+r>>1;
			int se3;
			if(se2<=mid) {
				se3=ask(l,mid);
				if(se3==se2) return solve(l,mid);
				else return solve(mid+1,r);
			}
			else {
				se3=ask(mid+1,r);
				if(se3==se2) return solve(mid+1,r);
				else return solve(l,mid);
			}
		}
		else {
			r=mid;mid=l+r>>1;
			int se3=ask(mid+1,se);
			if(se3==se) return solve(mid+1,r);
			else return solve(l,mid);
		}
	}
}
int n;
V solve() {
	s1=s2=0;
	cin>>n;
	cout<<"! "<<solve(1,n)<<endl;
}
char Ed;
int main() {
//	cerr<<"memory:"<<(&St-&Ed)/1024.0<<endl;
	int T;cin>>T;
	while(T--) solve();
//	cerr<<"time:"<<clock()<<endl;
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3560kb

input:

3
5

output:

! ? 1 5

result:

wrong answer format  Expected integer, but "?" found (test case 1)