QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138372#6394. Turn on the LightSchi2oidWA 5ms11500kbC++14945b2023-08-11 16:44:592023-08-11 16:45:02

Judging History

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

  • [2023-08-11 16:45:02]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:11500kb
  • [2023-08-11 16:44:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int ask(int x){
	int ret;
	cout<<"? "<<x<<endl;
	cin>>ret;
	return ret;
}
int id[2][2000005];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) id[0][i]=i;
	bool op=0;
	int bef=0;
	while(n>=4){
		int p1=n/4,p2=n-n/4;
		int x=ask(id[op][p1]);
		if(x==bef){
			cout<<"! "<<p1;
			return 0;
		}
		 int y=ask(id[op][p2]);
		 if(y==x){
		 	cout<<"! "<<p2;
		 	return 0;
		 }
		 int delta=y-bef;
		 op^=1;
		 if(delta==0){
		 	n=p2-p1;
		 	int cnt=0;
		 	for(int i=p1+1;i<p2;i++){
		 		id[op][++cnt]=id[op^1][i];
		 	}
		 }
		 else{
		 	n=n-p2+p1-1;
		 	int cnt=0;
		 	for(int i=1;i<p1;i++){
		 		id[op][++cnt]=id[op^1][i];
		 	}
		 	for(int i=p2+1;i<=n;i++){
		 		id[op][++cnt]=id[op^1][i];
		 	}
		 }
		 bef=y;
	}
	for(int i=1;i<=n;i++){
		int x=ask(id[op][i]);
		if(x==bef){
			cout<<"! "<<id[op][i];
			return 0;
		}
		bef=x;
	}
	return 0;
}

详细

Test #1:

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

input:

3
1
2
2

output:

? 1
? 2
? 3
! 3

result:

ok Correct position at 3

Test #2:

score: 0
Accepted
time: 2ms
memory: 5668kb

input:

10
1
0
1
0
1
0
0

output:

? 2
? 8
? 3
? 7
? 4
? 6
? 5
! 5

result:

ok Correct position at 5

Test #3:

score: 0
Accepted
time: 2ms
memory: 5620kb

input:

9
1
0
1
0
1
1

output:

? 2
? 7
? 3
? 6
? 4
? 5
! 5

result:

ok Correct position at 5

Test #4:

score: 0
Accepted
time: 1ms
memory: 5672kb

input:

8
1
0
1
0
0

output:

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

result:

ok Correct position at 4

Test #5:

score: 0
Accepted
time: 0ms
memory: 5632kb

input:

7
1
0
1
0
1
1

output:

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

result:

ok Correct position at 4

Test #6:

score: 0
Accepted
time: 1ms
memory: 5508kb

input:

6
1
0
1
0
0

output:

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

result:

ok Correct position at 3

Test #7:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

5
1
0
1
1

output:

? 1
? 4
? 2
? 3
! 3

result:

ok Correct position at 3

Test #8:

score: 0
Accepted
time: 0ms
memory: 3472kb

input:

4
1
1

output:

? 1
? 3
! 3

result:

ok Correct position at 3

Test #9:

score: 0
Accepted
time: 1ms
memory: 3472kb

input:

3
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #10:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

2
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #11:

score: 0
Accepted
time: 1ms
memory: 3340kb

input:

1
0

output:

? 1
! 1

result:

ok Correct position at 1

Test #12:

score: -100
Wrong Answer
time: 5ms
memory: 11500kb

input:

1000000
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1

output:

? 250000
? 750000
? 375000
? 625000
? 437500
? 562500
? 468750
? 531250
? 484375
? 515625
? 492187
? 507813
? 496093
? 503907
? 498046
? 501954
? 499023
? 500977
? 499511
? 500489
? 499755
? 500245
? 499877
? 500123
? 499938
? 500062
? 499969
? 500031
? 499984
? 500016
? 499992
? 500008
? 499996
? 5...

result:

wrong answer Wrong favorite light!