QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#371752#6394. Turn on the LightTANGTANGCCAC ✓2ms3920kbC++231.2kb2024-03-30 15:34:072024-03-30 15:34:08

Judging History

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

  • [2024-03-30 15:34:08]
  • 评测
  • 测评结果：AC
  • 用时：2ms
  • 内存：3920kb
查看
  • [2024-03-30 15:34:07]
  • 提交

answer

#include <bits/stdc++.h>
#include <sstream>

//#define int long long
#define endl '\n'
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;

using namespace std;

const int N=1e6+50;
int sz[N];
signed main() {
    int n,x;
    cin>>n;
    int a;
    printf("? 1\n");
    cin>>a;
    int l=1,r=n;
    if(a==0) {
        printf("! 1");
        return 0;
    }
    l=2;
    while(l<r) {
        //cout<<l<<' '<<r<<endl;
        int m=((l+r)>>1)+1;
        printf("? %d\n",m);
        cin>>x;
        if(x==0 and a==1) {
            a=x;
            r=m-1;
            //cout<<l<<' '<<r<<endl;
            printf("? %d\n",l);
            cin>>x;
            if(a==x) {
                printf("! %d", l);
                return 0;
            }
            else {
                l++;
                a=x;
                continue;
            }
        }
        if(x==a) {
            printf("! %d",m);
            return 0;
        }
        else if(x==a+1) {
            l=m+1;
        }
        else if(x==a-1) {
            r=m-1;
        }
        a=x;
    }
    printf("! %d",l);
    return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1
1

output:

? 1
? 3
! 3

result:

ok Correct position at 3

Test #2:

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

input:

10
1
0
1
0
1

output:

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

result:

ok Correct position at 4

Test #3:

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

input:

9
1
0
1
0
1

output:

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

result:

ok Correct position at 4

Test #4:

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

input:

8
1
0
1
0
1

output:

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

result:

ok Correct position at 4

Test #5:

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

input:

7
1
0
1
0
0

output:

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

result:

ok Correct position at 3

Test #6:

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

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: 0ms
memory: 3744kb

input:

5
1
0
1

output:

? 1
? 4
? 2
! 3

result:

ok Correct position at 3

Test #8:

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

input:

4
1
0
1

output:

? 1
? 4
? 2
! 3

result:

ok Correct position at 3

Test #9:

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

input:

3
1
0
0

output:

? 1
? 3
? 2
! 2

result:

ok Correct position at 2

Test #10:

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

input:

2
1

output:

? 1
! 2

result:

ok Correct position at 2

Test #11:

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

input:

1
0

output:

? 1
! 1

result:

ok Correct position at 1

Test #12:

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

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:

? 1
? 500002
? 2
? 250003
? 3
? 125004
? 4
? 62505
? 5
? 31256
? 6
? 15632
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #13:

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

input:

999999
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:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #14:

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

input:

999998
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:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #15:

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

input:

999997
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:

? 1
? 500000
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #16:

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

input:

999996
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:

? 1
? 500000
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #17:

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

input:

999995
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:

? 1
? 499999
? 2
? 250001
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #18:

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

input:

999994
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:

? 1
? 499999
? 2
? 250001
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #19:

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

input:

999993
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:

? 1
? 499998
? 2
? 250001
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #20:

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

input:

999992
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:

? 1
? 499998
? 2
? 250001
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #21:

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

input:

999991
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:

? 1
? 499997
? 2
? 250000
? 3
? 125002
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #22:

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

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
2
3
2
2

output:

? 1
? 500002
? 2
? 250003
? 3
? 125004
? 4
? 62505
? 5
? 31256
? 6
? 15632
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 40
? 44
? 43
! 43

result:

ok Correct position at 43

Test #23:

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

input:

999999
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
2
1
0
1
0
1
1

output:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 62
? 55
? 47
? 52
? 48
? 51
! 51

result:

ok Correct position at 51

Test #24:

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

input:

999998
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
2
1
0
1
0
1
1

output:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 62
? 55
? 47
? 52
? 48
? 51
! 51

result:

ok Correct position at 51

Test #25:

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

input:

999997
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
2
1
0
1
0
1
1

output:

? 1
? 500000
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 62
? 55
? 47
? 52
? 48
? 51
! 51

result:

ok Correct position at 51

Test #26:

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

input:

1000000
1
2
3
4
5
6
7
8
9
10
11
12
13
12
11
10
11
10
11
10

output:

? 1
? 500002
? 750002
? 875002
? 937502
? 968752
? 984377
? 992190
? 996096
? 998049
? 999026
? 999514
? 999758
? 999880
? 999820
? 999790
? 999775
? 999783
? 999780
? 999782
! 999781

result:

ok Correct position at 999781

Test #27:

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

input:

999999
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
16
15
14
13

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992189
? 996095
? 998048
? 999025
? 999513
? 999757
? 999879
? 999940
? 999971
? 999986
? 999979
? 999983
? 999982
? 999981
! 999980

result:

ok Correct position at 999980

Test #28:

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

input:

999998
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
16
15
14
13

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999939
? 999970
? 999985
? 999978
? 999982
? 999981
? 999980
! 999979

result:

ok Correct position at 999979

Test #29:

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

input:

999997
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
16
15
14
13

output:

? 1
? 500000
? 750000
? 875000
? 937500
? 968750
? 984375
? 992187
? 996093
? 998046
? 999023
? 999511
? 999755
? 999877
? 999938
? 999969
? 999984
? 999977
? 999981
? 999980
? 999979
! 999978

result:

ok Correct position at 999978

Test #30:

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

input:

1000000
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
13
12
11
11

output:

? 1
? 500002
? 2
? 250003
? 375003
? 437503
? 468753
? 484378
? 492191
? 496097
? 498050
? 499027
? 499515
? 499759
? 499881
? 499942
? 499973
? 499958
? 499951
? 499947
! 499947

result:

ok Correct position at 499947

Test #31:

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

input:

999999
1
2
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
2
3
4
3
2
2

output:

? 1
? 500001
? 750001
? 625002
? 500002
? 562503
? 500003
? 531254
? 500004
? 515630
? 500005
? 507818
? 500006
? 503913
? 500007
? 501961
? 500008
? 500985
? 500009
? 500498
? 500010
? 500255
? 500011
? 500134
? 500012
? 500074
? 500013
? 500044
? 500060
? 500068
? 500072
? 500071
? 500070
! 500070

result:

ok Correct position at 500070

Test #32:

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

input:

999998
1
2
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
0
1
0
0

output:

? 1
? 500001
? 750001
? 625002
? 500002
? 562503
? 500003
? 531254
? 500004
? 515630
? 500005
? 507818
? 500006
? 503913
? 500007
? 501961
? 500008
? 500985
? 500009
? 500498
? 500010
? 500255
? 500011
? 500134
? 500012
? 500074
? 500105
? 500090
? 500075
? 500083
? 500076
! 500076

result:

ok Correct position at 500076

Test #33:

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

input:

999997
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
13
14
15
14
13
12

output:

? 1
? 500000
? 2
? 250002
? 375002
? 437502
? 468752
? 484377
? 492189
? 496095
? 498048
? 499025
? 499513
? 499757
? 499879
? 499940
? 499971
? 499956
? 499964
? 499968
? 499967
? 499966
! 499965

result:

ok Correct position at 499965

Test #34:

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

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
0
0

output:

? 1
? 500002
? 2
? 250003
? 3
? 125004
? 4
? 62505
? 5
? 31256
? 6
? 15632
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
? 20
! 20

result:

ok Correct position at 20

Test #35:

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

input:

999999
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
0
0

output:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
? 20
! 20

result:

ok Correct position at 20

Test #36:

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

input:

999998
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
0
0

output:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
? 20
! 20

result:

ok Correct position at 20

Test #37:

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

input:

999997
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
0
0

output:

? 1
? 500000
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
? 20
! 20

result:

ok Correct position at 20

Test #38:

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

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:

? 1
? 500002
? 2
? 250003
? 3
? 125004
? 4
? 62505
? 5
? 31256
? 6
? 15632
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #39:

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

input:

999999
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:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #40:

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

input:

999998
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:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #41:

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

input:

999997
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:

? 1
? 500000
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7820
? 8
? 3915
? 9
? 1963
? 10
? 987
? 11
? 500
? 12
? 257
? 13
? 136
? 14
? 76
? 15
? 46
? 16
? 32
? 17
? 25
? 18
? 22
? 19
? 21
! 21

result:

ok Correct position at 21

Test #42:

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

input:

1000000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

output:

? 1
? 500002
? 750002
? 875002
? 937502
? 968752
? 984377
? 992190
? 996096
? 998049
? 999026
? 999514
? 999758
? 999880
? 999941
? 999972
? 999987
? 999995
? 999999
! 1000000

result:

ok Correct position at 1000000

Test #43:

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

input:

1000000
0

output:

? 1
! 1

result:

ok Correct position at 1
English 繁體中文 简体中文

Server Time: 2024-12-02 16:50:24 | OpenSource Project