QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641170#5702. Colorsatgc0 1ms3836kbC++231.5kb2024-10-14 18:58:422024-10-14 18:58:42

Judging History

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

  • [2024-10-14 18:58:42]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3836kb
  • [2024-10-14 18:58:42]
  • 提交

answer

#include<bits/stdc++.h>
#define int int64_t
using namespace std;
const int maxn = 2e5+10;
bool qry(int x){
	cout<<"? "<<x<<endl;
	bool res;cin>>res;return res;
}
void sol(){
	int n;cin>>n;
	int cur=0;

{
	int l=1,r=n;
	set<int>qed;
	qed.insert(cur);
	while(l<r){
		int md=(l+r)>>1;
		// if(stp^=1)cur+=md;
		// else cur-=md;
		// deb(cur+md,cur-md);
		if(cur+md>n)cur-=md;
		else if(cur-md<=0)cur+=md;
		else assert(0);
		// else if(qed.count(cur+md))cur-=md;
		// else if(abs(cur+md-(1+n)/2.) < abs(cur-md-(1+n)/2.))cur+=md;
		// else cur-=md;
		qed.insert(cur);
		if(0)r=md;
		else l=md+1;
	}
	cur=1-*qed.begin();
}

	int l=1,r=n;
	set<int>qed;
	qry(cur);qed.insert(cur);
	while(l<r){
		int md=(l+r)>>1;
		// if(stp^=1)cur+=md;
		// else cur-=md;
		// deb(cur+md,cur-md);
		while(cur+md>n&&cur-md<=0)--md;
		if(cur+md>n)cur-=md;
		else if(cur-md<=0)cur+=md;
		else if(qed.count(cur+md))cur-=md;
		else if(qed.count(cur-md))cur+=md;
		else if(abs(cur+md-(1+n)/2.) < abs(cur-md-(1+n)/2.))cur+=md;
		else cur-=md;
		qed.insert(cur);
		if(qry(cur))r=md;
		else l=md+1;
	}
	cout<<"= "<<r<<endl;
}

signed main() {
	// ios::sync_with_stdio(0),cin.tie(0);
	// int T;cin>>T;while(T--)
	sol();
	// const int n=8;
	// int len=n / 2;
	// int cur=0;int stp=0;
	// set<int>se;
	// while(len < n){
	// 	deb(len,cur);

	// 	assert(se.insert(cur).second);
	// 	if(stp^=1)cur+=len;
	// 	else cur-=len;
	// 	int nl=(1+len+n)/2;
	// 	len=nl;
	// }
	// se.insert(cur);

	// deb(se,se.size());
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 9
Accepted
time: 1ms
memory: 3484kb

input:

7
0
1
0
0

output:

? 3
? 7
? 5
? 2
= 4

result:

ok OK (4 queries)

Test #2:

score: 9
Accepted
time: 1ms
memory: 3600kb

input:

49
1
0
0
0
1
1
0

output:

? 16
? 41
? 4
? 47
? 1
? 46
? 2
= 45

result:

ok OK (7 queries)

Test #3:

score: 9
Accepted
time: 0ms
memory: 3600kb

input:

10
1
1
1
1
0

output:

? 4
? 9
? 6
? 8
? 7
= 2

result:

ok OK (5 queries)

Test #4:

score: 9
Accepted
time: 1ms
memory: 3572kb

input:

26
0
1
1
1
1
1

output:

? 10
? 23
? 16
? 12
? 14
? 13
= 1

result:

ok OK (6 queries)

Test #5:

score: 9
Accepted
time: 0ms
memory: 3604kb

input:

23
1
1
0
0
0

output:

? 8
? 20
? 14
? 5
? 16
= 12

result:

ok OK (5 queries)

Test #6:

score: 9
Accepted
time: 0ms
memory: 3580kb

input:

56
1
0
1
1
1
0
0

output:

? 19
? 47
? 5
? 40
? 8
? 38
? 7
= 32

result:

ok OK (7 queries)

Test #7:

score: 9
Accepted
time: 0ms
memory: 3792kb

input:

52
1
0
1
0
0
1
1

output:

? 17
? 43
? 4
? 37
? 1
? 39
? 2
= 37

result:

ok OK (7 queries)

Test #8:

score: 9
Accepted
time: 0ms
memory: 3536kb

input:

43
1
0
0
1
0
0

output:

? 15
? 37
? 4
? 42
? 6
? 43
= 38

result:

ok OK (6 queries)

Test #9:

score: 9
Accepted
time: 0ms
memory: 3836kb

input:

46
0
0
0
1
0
1

output:

? 16
? 39
? 4
? 45
? 7
? 46
= 39

result:

ok OK (6 queries)

Test #10:

score: 9
Accepted
time: 0ms
memory: 3536kb

input:

11
0
1
1
1
1

output:

? 4
? 10
? 7
? 5
? 6
= 1

result:

ok OK (5 queries)

Test #11:

score: 9
Accepted
time: 0ms
memory: 3600kb

input:

14
0
0
0
1
1

output:

? 5
? 12
? 1
? 14
? 2
= 12

result:

ok OK (5 queries)

Test #12:

score: 9
Accepted
time: 0ms
memory: 3796kb

input:

23
1
0
0
1
1
0

output:

? 8
? 20
? 2
? 23
? 3
? 22
= 20

result:

ok OK (6 queries)

Test #13:

score: 9
Accepted
time: 1ms
memory: 3592kb

input:

47
1
0
0
1
1
1
0

output:

? 16
? 40
? 4
? 46
? 7
? 45
? 8
= 38

result:

ok OK (7 queries)

Test #14:

score: 9
Accepted
time: 0ms
memory: 3824kb

input:

44
0
0
1
0
1
1
0

output:

? 15
? 37
? 4
? 32
? 1
? 31
? 2
= 30

result:

ok OK (7 queries)

Test #15:

score: 9
Accepted
time: 0ms
memory: 3488kb

input:

54
1
0
0
1
1
0
0

output:

? 18
? 45
? 4
? 52
? 7
? 50
? 6
= 45

result:

ok OK (7 queries)

Test #16:

score: 9
Accepted
time: 1ms
memory: 3536kb

input:

53
0
1
0
1
0
0

output:

? 17
? 44
? 30
? 9
? 27
? 7
= 21

result:

ok OK (6 queries)

Test #17:

score: 9
Accepted
time: 1ms
memory: 3596kb

input:

35
0
0
0
0
0
0

output:

? 12
? 30
? 3
? 34
? 1
? 35
= 35

result:

ok OK (6 queries)

Test #18:

score: 9
Accepted
time: 0ms
memory: 3480kb

input:

37
0
0
1
1
0
1

output:

? 12
? 31
? 3
? 27
? 5
? 28
= 23

result:

ok OK (6 queries)

Test #19:

score: 9
Accepted
time: 1ms
memory: 3820kb

input:

26
0
0
0
0
1
0

output:

? 10
? 23
? 3
? 26
? 1
? 25
= 25

result:

ok OK (6 queries)

Test #20:

score: 9
Accepted
time: 1ms
memory: 3512kb

input:

64
1
0
1
1
1
0
1

output:

? 22
? 54
? 6
? 46
? 10
? 44
? 9
= 35

result:

ok OK (7 queries)

Test #21:

score: 9
Accepted
time: 0ms
memory: 3544kb

input:

57
0
0
0
1
0
0

output:

? 19
? 48
? 5
? 55
? 8
? 57
= 50

result:

ok OK (6 queries)

Test #22:

score: 9
Accepted
time: 1ms
memory: 3792kb

input:

2
1
0

output:

? 1
? 2
= 2

result:

ok OK (2 queries)

Test #23:

score: 9
Accepted
time: 1ms
memory: 3632kb

input:

2
1
1

output:

? 1
? 2
= 1

result:

ok OK (2 queries)

Test #24:

score: 9
Accepted
time: 1ms
memory: 3596kb

input:

3
0
0

output:

? 1
? 3
= 3

result:

ok OK (2 queries)

Test #25:

score: 9
Accepted
time: 1ms
memory: 3596kb

input:

3
0
1
0

output:

? 1
? 3
? 2
= 2

result:

ok OK (3 queries)

Test #26:

score: 9
Accepted
time: 1ms
memory: 3752kb

input:

3
0
1
1

output:

? 1
? 3
? 2
= 1

result:

ok OK (3 queries)

Test #27:

score: 9
Accepted
time: 1ms
memory: 3572kb

input:

4
0
0
0

output:

? 2
? 4
? 1
= 4

result:

ok OK (3 queries)

Test #28:

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

input:

4
0
0
1

output:

? 2
? 4
? 1
= 3

result:

ok OK (3 queries)

Test #29:

score: 9
Accepted
time: 1ms
memory: 3596kb

input:

4
0
1
0

output:

? 2
? 4
? 3
= 2

result:

ok OK (3 queries)

Test #30:

score: 9
Accepted
time: 1ms
memory: 3532kb

input:

4
0
1
1

output:

? 2
? 4
? 3
= 1

result:

ok OK (3 queries)

Test #31:

score: 9
Accepted
time: 1ms
memory: 3580kb

input:

5
1
0
0

output:

? 2
? 5
? 1
= 5

result:

ok OK (3 queries)

Test #32:

score: 9
Accepted
time: 0ms
memory: 3600kb

input:

5
1
0
1

output:

? 2
? 5
? 1
= 4

result:

ok OK (3 queries)

Test #33:

score: 9
Accepted
time: 0ms
memory: 3592kb

input:

5
1
1
0

output:

? 2
? 5
? 3
= 3

result:

ok OK (3 queries)

Test #34:

score: 9
Accepted
time: 0ms
memory: 3596kb

input:

5
1
1
1
0

output:

? 2
? 5
? 3
? 4
= 2

result:

ok OK (4 queries)

Test #35:

score: 9
Accepted
time: 0ms
memory: 3760kb

input:

5
1
1
1
1

output:

? 2
? 5
? 3
? 4
= 1

result:

ok OK (4 queries)

Test #36:

score: 9
Accepted
time: 0ms
memory: 3536kb

input:

6
1
0
0

output:

? 3
? 6
? 1
= 6

result:

ok OK (3 queries)

Test #37:

score: 9
Accepted
time: 0ms
memory: 3600kb

input:

6
1
0
1
0

output:

? 3
? 6
? 1
? 5
= 5

result:

ok OK (4 queries)

Test #38:

score: 9
Accepted
time: 1ms
memory: 3600kb

input:

6
1
0
1
1

output:

? 3
? 6
? 1
? 5
= 4

result:

ok OK (4 queries)

Test #39:

score: 9
Accepted
time: 1ms
memory: 3536kb

input:

6
1
1
0

output:

? 3
? 6
? 4
= 3

result:

ok OK (3 queries)

Test #40:

score: 9
Accepted
time: 1ms
memory: 3528kb

input:

6
1
1
1
0

output:

? 3
? 6
? 4
? 5
= 2

result:

ok OK (4 queries)

Test #41:

score: 9
Accepted
time: 0ms
memory: 3832kb

input:

6
1
1
1
1

output:

? 3
? 6
? 4
? 5
= 1

result:

ok OK (4 queries)

Test #42:

score: 9
Accepted
time: 0ms
memory: 3572kb

input:

7
0
0
0

output:

? 3
? 7
? 1
= 7

result:

ok OK (3 queries)

Test #43:

score: 9
Accepted
time: 0ms
memory: 3600kb

input:

7
0
0
1
0

output:

? 3
? 7
? 1
? 6
= 6

result:

ok OK (4 queries)

Test #44:

score: 9
Accepted
time: 1ms
memory: 3484kb

input:

7
0
0
1
1

output:

? 3
? 7
? 1
? 6
= 5

result:

ok OK (4 queries)

Test #45:

score: 9
Accepted
time: 0ms
memory: 3572kb

input:

7
0
1
0
0

output:

? 3
? 7
? 5
? 2
= 4

result:

ok OK (4 queries)

Test #46:

score: 9
Accepted
time: 0ms
memory: 3832kb

input:

7
0
1
0
1

output:

? 3
? 7
? 5
? 2
= 3

result:

ok OK (4 queries)

Test #47:

score: 9
Accepted
time: 0ms
memory: 3632kb

input:

7
0
1
1
0

output:

? 3
? 7
? 5
? 4
= 2

result:

ok OK (4 queries)

Test #48:

score: 9
Accepted
time: 0ms
memory: 3568kb

input:

7
0
1
1
1

output:

? 3
? 7
? 5
? 4
= 1

result:

ok OK (4 queries)

Test #49:

score: 9
Accepted
time: 0ms
memory: 3576kb

input:

8
1
0
0
0

output:

? 3
? 7
? 1
? 8
= 8

result:

ok OK (4 queries)

Test #50:

score: 9
Accepted
time: 1ms
memory: 3660kb

input:

8
1
0
0
1

output:

? 3
? 7
? 1
? 8
= 7

result:

ok OK (4 queries)

Test #51:

score: 9
Accepted
time: 0ms
memory: 3596kb

input:

8
1
0
1
0

output:

? 3
? 7
? 1
? 6
= 6

result:

ok OK (4 queries)

Test #52:

score: 9
Accepted
time: 0ms
memory: 3832kb

input:

8
1
0
1
1

output:

? 3
? 7
? 1
? 6
= 5

result:

ok OK (4 queries)

Test #53:

score: 9
Accepted
time: 0ms
memory: 3760kb

input:

8
1
1
0
0

output:

? 3
? 7
? 5
? 2
= 4

result:

ok OK (4 queries)

Test #54:

score: 9
Accepted
time: 1ms
memory: 3532kb

input:

8
1
1
0
1

output:

? 3
? 7
? 5
? 2
= 3

result:

ok OK (4 queries)

Test #55:

score: 9
Accepted
time: 0ms
memory: 3596kb

input:

8
1
1
1
0

output:

? 3
? 7
? 5
? 4
= 2

result:

ok OK (4 queries)

Test #56:

score: 9
Accepted
time: 0ms
memory: 3604kb

input:

8
1
1
1
1

output:

? 3
? 7
? 5
? 4
= 1

result:

ok OK (4 queries)

Test #57:

score: 9
Accepted
time: 0ms
memory: 3576kb

input:

18
0
0
0
0
1

output:

? 7
? 16
? 2
? 18
? 1
= 17

result:

ok OK (5 queries)

Test #58:

score: 9
Accepted
time: 0ms
memory: 3632kb

input:

18
0
0
0
0
0

output:

? 7
? 16
? 2
? 18
? 1
= 18

result:

ok OK (5 queries)

Test #59:

score: 9
Accepted
time: 0ms
memory: 3600kb

input:

37
0
0
0
0
0
1

output:

? 12
? 31
? 3
? 36
? 1
? 37
= 36

result:

ok OK (6 queries)

Test #60:

score: 9
Accepted
time: 0ms
memory: 3596kb

input:

37
0
0
0
0
0
0

output:

? 12
? 31
? 3
? 36
? 1
? 37
= 37

result:

ok OK (6 queries)

Test #61:

score: 9
Accepted
time: 0ms
memory: 3792kb

input:

63
1
1
1
1
1
1
1

output:

? 21
? 53
? 37
? 29
? 33
? 31
? 32
= 1

result:

ok OK (7 queries)

Test #62:

score: 9
Accepted
time: 0ms
memory: 3484kb

input:

63
1
0
0
0
0
0

output:

? 21
? 53
? 5
? 61
? 1
? 63
= 63

result:

ok OK (6 queries)

Test #63:

score: 9
Accepted
time: 1ms
memory: 3540kb

input:

63
1
1
1
1
1
1
0

output:

? 21
? 53
? 37
? 29
? 33
? 31
? 32
= 2

result:

ok OK (7 queries)

Test #64:

score: 9
Accepted
time: 0ms
memory: 3640kb

input:

63
1
0
0
0
0
1
0

output:

? 21
? 53
? 5
? 61
? 1
? 63
? 2
= 62

result:

ok OK (7 queries)

Test #65:

score: 9
Accepted
time: 1ms
memory: 3488kb

input:

63
1
1
1
1
1
0
1

output:

? 21
? 53
? 37
? 29
? 33
? 31
? 34
= 3

result:

ok OK (7 queries)

Test #66:

score: 9
Accepted
time: 1ms
memory: 3536kb

input:

63
1
0
0
0
0
1
1

output:

? 21
? 53
? 5
? 61
? 1
? 63
? 2
= 61

result:

ok OK (7 queries)

Test #67:

score: 9
Accepted
time: 0ms
memory: 3628kb

input:

63
1
1
1
1
1
0
0

output:

? 21
? 53
? 37
? 29
? 33
? 31
? 34
= 4

result:

ok OK (7 queries)

Test #68:

score: 0
Wrong Answer
time: 0ms
memory: 3536kb

input:

63
1
0
0
0
1
0
0
0

output:

? 21
? 53
? 5
? 61
? 1
? 59
? 1
? 60
= 60

result:

wrong answer Hair color 1 was used multiple times

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%