QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#460655#8239. Mysterious TreeCRN2010TL 1ms3672kbC++202.9kb2024-07-01 23:44:222024-07-01 23:44:22

Judging History

你现在查看的是最新测评结果

  • [2024-07-01 23:44:22]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3672kb
  • [2024-07-01 23:44:22]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std ;


void solve() {
	int n , op ;
	cin >> n ;
	
	for(int i = 2 ; i <= n ; i += 2)
	{
		cout << "? " << i << ' ' << i - 1 << endl ;
		cin >> op ;
		if (op)
		{
			if ( i == n ) {
				cout << "? " << 1 << ' ' << i << endl ;
				cin >> op ;
				if ( op ) {
					cout << "? " << 2 << ' ' << i << endl ;
					cin >> op ;
					if ( op ) {
						cout << "! 2" << endl ;
						return ;
					} else {
						cout << "! 1" << endl ;
						return ;
					}
				} else {
					cout << "? " << 1 << ' ' << i - 1 << endl ;
					cin >> op ;
					if ( op ) {
						cout << "? " << 2 << ' ' << i - 1 << endl ;
						cin >> op ;
						if ( op ) {
							cout << "! 2" << endl ;
							return ;
						} else {
							cout << "! 1" << endl ;
							return ;
						}
					} else {
						cout << "! 1" << endl ;
						return ;
					}
				}
			} else {
				cout << "? " << i << ' ' << n << endl ;
				cin >> op ;
				if ( op ) {
					if ( i == n - 1 ) {
						cout << "? " << 1 << ' ' << i << endl ;
						cin >> op ;
						if ( op ) {
							cout << "! 2" << endl ;
							return ;
						} else {
							cout << "! 1" << endl ;
							return ;
						}
					} else {
						cout << "? " << i << ' ' << n - 1 << endl ; 
						cin >> op ;
						if ( op ) {
							cout << "! 2" << endl ;
							return ;
						} else {
							cout << "! 1" << endl ;
							return ;
						}
					}
				} else {
					cout << "? " << i - 1 << ' ' << n << endl ;
					cin >> op ;
					if ( op ) {
						if ( i == n - 1 ) {
							cout << "? " << 1 << ' ' << i - 1 << endl ;
							cin >> op ;
							if ( op ) {
								cout << "! 2" << endl ;
								return ;
							} else {
								cout << "! 1" << endl ;
								return ;
							}							
						} else {
							cout << "? " << i - 1 << ' ' << n - 1 << endl ; 
							cin >> op ;
							if ( op ) {
								cout << "! 2" << endl ;
								return ;
							} else {
								cout << "! 1" << endl ;
								return ;
							}
						}
					} else {
						cout << "! 1" << endl ;
						return ;
					}
				}
			}
		}
	}
	if ( n & 1 ) {
		cout << "? " << n - 1 << ' ' << n << endl ;
		cin >> op ;
		cout << "? " << 1 << ' ' << n << endl ;
		cin >> op ;
		if ( op ) {
			cout << "? " << 2 << ' ' << n << endl ;
			cin >> op ; 
			if ( op ) {
				cout << "! 2" << endl ;
				return ;
			} else {
				cout << "! 1" << endl ;
				return ;
			}
		} else {
			cout << "? " << 1 << ' ' << n - 1 << endl ;
			cin >> op ;
			if (op) {
				cout << "? " << 2 << ' ' << n - 1 << endl ; 
				cin >> op ;
				if ( op ) {
					cout << "! 2" << endl ;
					return ;
				} else {
					cout << "! 1" << endl ;
					return ; 
				}
			} else {
				cout << "! 1" << endl ;
				return ;
			}
		}
	}
}

int main() 
{
	int t ;
	cin >> t ;
	while (t--)
	{
		solve() ;
	}
	return 0 ; 
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3672kb

input:

2
4
1
0
0
4
0
1
0
1
1

output:

? 2 1
? 2 4
? 1 4
! 1
? 2 1
? 4 3
? 1 4
? 1 3
? 2 3
! 2

result:

ok Correct (2 test cases)

Test #2:

score: -100
Time Limit Exceeded

input:

87
13
0
0
0
0
0
1
1
1
15
0
0
0
0
0
0
1
0
1
1
7
0
0
0
1
1
1
15
0
0
0
1
1
0
19
0
0
0
0
0
1
0
1
1
20
0
0
0
0
0
0
0
0
0
0

output:

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

result: