QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#883124#9734. Identify ChordlsxhyydsWA 0ms3712kbC++146.0kb2025-02-05 14:47:462025-02-05 14:47:59

Judging History

This is the latest submission verdict.

  • [2025-02-05 14:47:59]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3712kb
Show
  • [2025-02-05 14:47:46]
  • Submitted

answer

//#ifndef fio
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse3","sse2","sse")
//#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
//#pragma GCC target("f16c")
//#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
//#pragma GCC diagnostic error "-fwhole-program"
//#pragma GCC diagnostic error "-fcse-skip-blocks"
//#pragma GCC diagnostic error "-funsafe-loop-optimizations"
//#pragma GCC diagnostic error "-std=c++20"
//#endif
#include <bits/stdc++.h>
#define N 1000005
#define M 3000005
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define i128 __int128
#define mk make_pair
#define x first
#define y second
//#define bas 20200721
//#define bas 1000000007
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define VI vector<int>
#define VL vector<ll>
#define lowbit(x) (x&(-x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PIL pair<int,ll>
#define PLI pair<ll,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define PVL pair<VI,ll>
#define eps (1e-9)
#define mod 1000000007
//#define double long double
//#define int long long
using namespace std;
//int mod=998244353;
const double Pi=acos(-1);
struct mint {
	int x;
	mint() : x(0) {}
	mint(long long y, bool flag = 0) {
		if (flag) x = (int)(y);
		else x = (int)((y % mod + mod) % mod);
	}
	friend const mint ksm(mint a, long long b);
	const mint inv() {return ksm(*this, mod - 2);}
};
bool operator == (const mint a, const mint b) {return a.x == b.x;}
bool operator != (const mint a, const mint b) {return a.x != b.x;}
bool operator <(const mint a,const mint b){return a.x<b.x;}
bool operator >(const mint a,const mint b){return a.x>b.x;}
int operator ! (const mint a) {return !a.x;}
const mint operator + (const mint a, const mint b) {
	mint res(a.x + b.x, 1);
	if (res.x >= mod) res.x -= mod;
	return res;
}
mint& operator += (mint &a, const mint b) {
	a.x += b.x;
	if (a.x >= mod) a.x -= mod;
	return a;
}
const mint operator - (const mint a, const mint b) {
	mint res(a.x - b.x, 1);
	if (res.x < 0) res.x += mod;
	return res;
}
mint& operator -= (mint &a, const mint b) {
	a.x -= b.x;
	if (a.x < 0) a.x += mod;
	return a;
}
const mint operator * (const mint a, const mint b) {
	return mint((long long)a.x * b.x % mod, 1);
}
mint& operator *= (mint &a, const mint b) {
	a.x = (int)((long long)a.x * b.x % mod);
	return a;
}
const mint ksm(mint a, long long b) {
	mint res(1, 1);
	for (; b; a *= a, b >>= 1)
		if (b & 1) res *= a;
	return res;
}
const mint operator / (const mint a, const mint b) {
	return a * ksm(b, mod - 2);
}
mint& operator /= (mint &a, const mint b) {
	a = a * ksm(b, mod - 2);
	return a;
}
ostream& operator << (ostream &out, const mint a) {
	return out << a.x;
}
istream& operator >> (istream &in, mint &a) {
	long long y;
	in >> y, a = mint(y);
	return in;
}
PLL operator +(PLL a,PLL b){
	return mk(a.x+b.x,a.y+b.y);
}
PLL operator +=(PLL &a,const PLL b){
	a=a+b;
	return a;
}
PLL operator *(PLL a,int b){
	a=mk(a.x*b,a.y*b);
	return a;
}
void chkmx(ll &x,ll y){
	x=max(x,y);
}
void chkmn(ll &x,ll y){
	x=min(x,y);
}

int tt;
int n,m,q,k;
string s;
int a[N];
int qy(int x,int y){
	cout<<"? "<<x<<' '<<y<<'\n';
	cout.flush();
	int p;
	cin>>p;
	return p;
}
int lst(int x,int y){
	--x;
	x-=y;
	x=(x%n+n)%n;
	return x+1;
}
int nxt(int x,int y){
	--x;
	x+=y;
	x%=n;
	return x+1;
}
int dis(int x,int y){
	if(x<=y)return y-x;
	return n-x+y;
}
mt19937 rd(time(0));
void solve(){
	cin>>n;
	int x=1,y=x+n/2;
	int z1=qy(x,y);
	// swap(nxt,lst);
	if(z1==n/2){++x;++y;
		z1=qy(x,y);
		// assert(z1!=n/2);
		if(z1==n/2){
			x=nxt(x,1);
			y=nxt(y,1);
			z1=qy(x,y);
		}
	}
	if(z1==n/2){
		int x=1,y=lst(x,n/2);
		int z1=qy(x,y);
		assert(n%2==1);
		// swap(nxt,lst);
		if(z1==n/2){
			x=lst(x,1);
			y=lst(y,1);
			z1=qy(x,y);
			// assert(z1!=n/2);
			if(z1==n/2){
				x=lst(x,1);
				y=lst(y,1);
				z1=qy(x,y);
			}
		}
		assert(z1!=n/2);
		if(z1==1){
			cout<<"! "<<x<<' '<<y<<'\n';
			cout.flush();
			return ;
		}
		int qi=-1;		
	// cerr<<" "<<x<<' '<<y<<"[[\n";
		if(qy(nxt(x,1),y)<z1){
			// cerr<<"pp\n";
			int l=1,r=n-n/2,ans=-1;
			// int 
			while(l<=r){
				int mid=(l+r)>>1;
				if(qy(nxt(x,mid),y)==z1-mid){
					ans=mid;l=mid+1;
				}
				else
					r=mid-1;
			}
			qi=nxt(x,ans);
		}
		else{
			// cerr<<"jj\n";
			int l=0,r=n/2,ans=0;
			while(l<=r){
				int mid=(l+r)>>1;
				if(qy(lst(x,mid),y)==z1-mid){
					ans=mid;l=mid+1;
				}
				else
					r=mid-1;
			}
			qi=lst(x,ans);
		}
		int dd=qy(qi,nxt(qi,n/2));
		int shi=n/2-dd+1;
		if(qy(qi,nxt(qi,shi))==1)cout<<"! "<<qi<<" "<<nxt(qi,shi)<<'\n';
		else{
			cout<<"! "<<qi<<' '<<nxt(nxt(qi,n/2),dd-1)<<'\n';
		}
		return ;
	}
	assert(z1!=n/2);
	if(z1==1){
		cout<<"! "<<x<<' '<<y<<'\n';
		cout.flush();
		return ;
	}
	int qi=-1;
	// cerr<<" "<<x<<' '<<y<<"[[\n";
	if(qy(lst(x,1),y)<z1){
		// cerr<<"pp\n";
		int l=1,r=n-n/2,ans=-1;
		// int 
		while(l<=r){
			int mid=(l+r)>>1;
			if(qy(lst(x,mid),y)==z1-mid){
				ans=mid;l=mid+1;
			}
			else
				r=mid-1;
		}
		qi=lst(x,ans);
	}
	else{
		// cerr<<"jj\n";
		int l=0,r=n/2,ans=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(qy(nxt(x,mid),y)==z1-mid){
				ans=mid;l=mid+1;
			}
			else
				r=mid-1;
		}
		qi=nxt(x,ans);
	}
	if(n%2==0){
		int dd=qy(qi,nxt(qi,n/2));
		int shi=n/2-dd+1;
		// cerr<<qi<<' '<<dd<<' '<<shi<<";;\n";
		if(qy(qi,nxt(qi,shi))==1)cout<<"! "<<qi<<" "<<nxt(qi,shi)<<'\n';
		else cout<<"! "<<qi<<" "<<lst(qi,shi)<<'\n';
		cout.flush();
	}
	else{
		int dd=qy(qi,nxt(qi,n/2));
		int shi=n/2-dd+1;
		if(qy(qi,nxt(qi,shi))==1)cout<<"! "<<qi<<" "<<nxt(qi,shi)<<'\n';
		else{
			cout<<"! "<<qi<<' '<<nxt(nxt(qi,n/2),dd-1)<<'\n';
		}
	}
}
signed main(){
	// freopen("line.in","r",stdin);
	// freopen("line.out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0),cout.tie(0);
	cin>>tt;
	while(tt--){
		solve();
		int p;
		cin>>p;
	}	
	return 0;
}
/*

*/
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

2
6
2
2
1
1
2
1
1
4
1
1

output:

? 1 4
? 6 4
? 2 4
? 3 4
? 2 5
? 2 4
! 2 4
? 1 3
! 1 3

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3712kb

input:

1000
15
5
6
2
2
1
5
1
1
19
5
6
5
4
3
4
1
1
1
17
5
6
4
4
3
4
1
1
1
15
6
7
4
6
6
6
1
1
14
5
6
4
4
5
5
1
1
15
3
4
4
2
3
1
1
1
17
8
8
6
7
4
5
4
5
2
3
1
20
6
7
5
8
6
7
6
1
1
13
5
4
3
3
2
3
4
1
18
3
2
4
3
2
3
5
1
13
4
3
3
4
3
4
3
1
14
2
1
3
2
1
2
3
1
17
8
6
7
2
2
3
4
1
1
12
5
5
3
4
3
1
1
1
10
5
5
3
4
1
1
...

output:

? 1 8
? 15 8
? 4 8
? 6 8
? 5 8
? 5 12
? 5 8
! 5 8
? 1 10
? 19 10
? 5 10
? 2 10
? 3 10
? 4 10
? 3 12
? 3 12
! 3 12
? 1 9
? 17 9
? 5 9
? 2 9
? 3 9
? 4 9
? 3 11
? 3 11
! 3 11
? 1 8
? 15 8
? 4 8
? 2 8
? 1 8
? 1 8
? 1 3
! 1 3
? 1 8
? 14 8
? 4 8
? 2 8
? 3 8
? 2 9
? 2 5
! 2 5
? 1 8
? 15 8
? 4 8
? 2 8
? 3 8...

result:

wrong answer Wrong answer n=15, actual=11-13, guessed=13-14 (test case 43)
English 繁體中文 简体中文

服务器时间: 2025-02-08 18:05:18 | 开源项目