QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106200#6394. Turn on the Lightblzgods#AC ✓5ms3748kbC++11884b2023-05-16 21:29:362023-05-16 21:29:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-16 21:29:37]
  • 评测
  • 测评结果：AC
  • 用时：5ms
  • 内存：3748kb
查看
  • [2023-05-16 21:29:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;

int query(int x)
{
    printf("? %d\n",x);fflush(stdout);scanf("%d",&x);return x;
}
void print(int x)
{
    printf("! %d\n",x);
    fflush(stdout);
}
void solve()
{
    int n;scanf("%d",&n);
    int lst=0;
    int l=1,r=n;
    while(1)
    {
        int now=query(l);
        if(now==lst){print(l);return ;}
        l=l+1;
        lst=now;
        while(l<r)
        {
            int mid=l+r>>1;
            int now=query(mid);
            if(now==lst){print(mid);return ;}
            if(now>lst)
            {
                l=mid+1;lst=now;
            }
            else
            {
                r=mid-1;lst=now;break;
            }
        }
        if(l==r){print(l);return ;}
    }
}
int main()
{
    int T=1;
    while(T--)solve();
}
Source code, Language: C++11

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1
2

output:

? 1
? 2
! 3

result:

ok Correct position at 3

Test #2:

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

input:

10
1
0
1
0

output:

? 1
? 6
? 2
? 4
! 3

result:

ok Correct position at 3

Test #3:

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

input:

9
1
2
3
3

output:

? 1
? 5
? 7
? 8
! 8

result:

ok Correct position at 8

Test #4:

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

input:

8
1
0
1
1

output:

? 1
? 5
? 2
? 3
! 3

result:

ok Correct position at 3

Test #5:

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

input:

7
1
2
3

output:

? 1
? 4
? 6
! 7

result:

ok Correct position at 7

Test #6:

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

input:

6
1
0
1

output:

? 1
? 4
? 2
! 3

result:

ok Correct position at 3

Test #7:

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

input:

5
1
2
3

output:

? 1
? 3
? 4
! 5

result:

ok Correct position at 5

Test #8:

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

input:

4
1
1

output:

? 1
? 3
! 3

result:

ok Correct position at 3

Test #9:

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

input:

3
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #10:

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

input:

2
1

output:

? 1
! 2

result:

ok Correct position at 2

Test #11:

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

input:

1
0

output:

? 1
! 1

result:

ok Correct position at 1

Test #12:

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

input:

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

output:

? 1
? 500001
? 2
? 250001
? 375001
? 437501
? 375002
? 406251
? 421876
? 406252
? 414064
? 406253
? 410158
? 412111
? 413087
? 413575
? 413819
? 413941
? 414002
? 414033
? 414003
? 414018
? 414004
? 414011
? 414005
? 414008
? 414009
! 414010

result:

ok Correct position at 414010

Test #13:

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

input:

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

output:

? 1
? 500000
? 750000
? 875000
? 750001
? 812500
? 843750
? 812501
? 828125
? 835937
? 839843
? 841796
? 842773
? 843261
? 843505
? 843627
? 843688
? 843719
? 843734
? 843742
? 843735
? 843738
? 843740
! 843740

result:

ok Correct position at 843740

Test #14:

score: 0
Accepted
time: 4ms
memory: 3720kb

input:

999998
1
0
1
0
1
0
1
0
1
2
3
4
5
6
5
6
7
8
9
8
9
8
9
10
11
12
12

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 46878
? 54690
? 58596
? 60549
? 61526
? 60550
? 61038
? 61282
? 61404
? 61465
? 61405
? 61435
? 61406
? 61420
? 61427
? 61431
? 61433
! 61433

result:

ok Correct position at 61433

Test #15:

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

input:

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

output:

? 1
? 499999
? 749998
? 874998
? 749999
? 812498
? 843748
? 812499
? 828123
? 835935
? 839841
? 841794
? 842771
? 843259
? 843503
? 843625
? 843686
? 843717
? 843732
? 843740
? 843733
? 843736
? 843738
! 843738

result:

ok Correct position at 843738

Test #16:

score: 0
Accepted
time: 4ms
memory: 3564kb

input:

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

output:

? 1
? 499999
? 2
? 250000
? 374999
? 437499
? 375000
? 406249
? 421874
? 406250
? 414062
? 406251
? 410156
? 412109
? 413085
? 413573
? 413817
? 413939
? 414000
? 414031
? 414001
? 414016
? 414002
? 414009
? 414003
? 414006
? 414007
! 414008

result:

ok Correct position at 414008

Test #17:

score: 0
Accepted
time: 4ms
memory: 3668kb

input:

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

output:

? 1
? 499998
? 749997
? 874996
? 937496
? 968746
? 937497
? 953121
? 960933
? 964839
? 966792
? 967769
? 966793
? 967281
? 967525
? 967282
? 967403
? 967464
? 967494
? 967509
? 967517
? 967510
? 967513
? 967515
! 967514

result:

ok Correct position at 967514

Test #18:

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

input:

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

output:

? 1
? 499998
? 2
? 250000
? 3
? 125001
? 187500
? 218750
? 187501
? 203125
? 210937
? 214843
? 216796
? 217773
? 218261
? 218505
? 218627
? 218688
? 218719
? 218734
? 218742
? 218735
? 218738
? 218740
! 218739

result:

ok Correct position at 218739

Test #19:

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

input:

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

output:

? 1
? 499997
? 749995
? 874994
? 937494
? 968744
? 937495
? 953119
? 960931
? 964837
? 966790
? 967767
? 966791
? 967279
? 967523
? 967280
? 967401
? 967462
? 967492
? 967507
? 967515
? 967508
? 967511
? 967513
! 967512

result:

ok Correct position at 967512

Test #20:

score: 0
Accepted
time: 4ms
memory: 3500kb

input:

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

output:

? 1
? 499997
? 2
? 249999
? 374998
? 437497
? 468747
? 437498
? 453122
? 460934
? 464840
? 466793
? 467770
? 468258
? 468502
? 468624
? 468685
? 468716
? 468731
? 468739
? 468732
? 468735
? 468737
! 468737

result:

ok Correct position at 468737

Test #21:

score: 0
Accepted
time: 5ms
memory: 3560kb

input:

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

output:

? 1
? 499996
? 749994
? 874993
? 749995
? 812494
? 749996
? 781245
? 749997
? 765621
? 773433
? 765622
? 769527
? 771480
? 772456
? 772944
? 773188
? 773310
? 773371
? 773402
? 773372
? 773387
? 773373
? 773380
? 773374
? 773377
? 773378
! 773379

result:

ok Correct position at 773379

Test #22:

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

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
4
5

output:

? 1
? 500001
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7818
? 8
? 3913
? 9
? 1961
? 10
? 985
? 11
? 498
? 12
? 255
? 13
? 134
? 14
? 74
? 15
? 44
? 16
? 30
? 37
? 40
? 42
! 43

result:

ok Correct position at 43

Test #23:

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

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

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7818
? 8
? 3913
? 9
? 1961
? 10
? 985
? 11
? 498
? 12
? 255
? 13
? 134
? 14
? 74
? 15
? 44
? 59
? 45
? 52
? 46
? 49
? 50
! 51

result:

ok Correct position at 51

Test #24:

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

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

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7818
? 8
? 3913
? 9
? 1961
? 10
? 985
? 11
? 498
? 12
? 255
? 13
? 134
? 14
? 74
? 15
? 44
? 59
? 45
? 52
? 46
? 49
? 50
! 51

result:

ok Correct position at 51

Test #25:

score: 0
Accepted
time: 3ms
memory: 3508kb

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

output:

? 1
? 499999
? 2
? 250000
? 3
? 125001
? 4
? 62502
? 5
? 31253
? 6
? 15629
? 7
? 7818
? 8
? 3913
? 9
? 1961
? 10
? 985
? 11
? 498
? 12
? 255
? 13
? 134
? 14
? 74
? 15
? 44
? 59
? 45
? 52
? 46
? 49
? 50
! 51

result:

ok Correct position at 51

Test #26:

score: 0
Accepted
time: 3ms
memory: 3716kb

input:

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

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999757
? 999817
? 999758
? 999787
? 999759
? 999773
? 999780
? 999783
? 999781
! 999781

result:

ok Correct position at 999781

Test #27:

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

input:

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

output:

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

result:

ok Correct position at 999980

Test #28:

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

input:

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

output:

? 1
? 500000
? 749999
? 874999
? 937499
? 968749
? 984374
? 992186
? 996092
? 998045
? 999022
? 999510
? 999754
? 999876
? 999937
? 999968
? 999983
? 999969
? 999976
? 999979
! 999979

result:

ok Correct position at 999979

Test #29:

score: 0
Accepted
time: 3ms
memory: 3560kb

input:

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

output:

? 1
? 499999
? 749998
? 874998
? 937498
? 968748
? 984373
? 992185
? 996091
? 998044
? 999021
? 999509
? 999753
? 999875
? 999936
? 999967
? 999982
? 999968
? 999975
? 999978
! 999978

result:

ok Correct position at 999978

Test #30:

score: 0
Accepted
time: 3ms
memory: 3492kb

input:

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

output:

? 1
? 500001
? 2
? 250001
? 375001
? 437501
? 468751
? 484376
? 492188
? 496094
? 498047
? 499024
? 499512
? 499756
? 499878
? 499939
? 499970
? 499940
? 499955
? 499941
? 499948
? 499942
? 499945
? 499946
! 499947

result:

ok Correct position at 499947

Test #31:

score: 0
Accepted
time: 4ms
memory: 3508kb

input:

999999
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
3
4
5
6
6

output:

? 1
? 500000
? 750000
? 500001
? 625000
? 500002
? 562501
? 500003
? 531252
? 500004
? 515628
? 500005
? 507816
? 500006
? 503911
? 500007
? 501959
? 500008
? 500983
? 500009
? 500496
? 500010
? 500253
? 500011
? 500132
? 500012
? 500072
? 500013
? 500042
? 500057
? 500064
? 500068
? 500070
! 500070

result:

ok Correct position at 500070

Test #32:

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

input:

999998
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
3
2
3
2
3
2
3
2

output:

? 1
? 500000
? 749999
? 500001
? 625000
? 500002
? 562501
? 500003
? 531252
? 500004
? 515628
? 500005
? 507816
? 500006
? 503911
? 500007
? 501959
? 500008
? 500983
? 500009
? 500496
? 500010
? 500253
? 500011
? 500132
? 500012
? 500072
? 500102
? 500073
? 500087
? 500074
? 500080
? 500075
? 500077...

result:

ok Correct position at 500076

Test #33:

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

input:

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

output:

? 1
? 499999
? 2
? 250000
? 374999
? 437499
? 468749
? 484374
? 492186
? 496092
? 498045
? 499022
? 499510
? 499754
? 499876
? 499937
? 499968
? 499938
? 499953
? 499960
? 499964
? 499966
! 499965

result:

ok Correct position at 499965

Test #34:

score: 0
Accepted
time: 4ms
memory: 3504kb

input:

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

output:

? 1
? 500001
? 2
? 250001
? 375001
? 250002
? 312501
? 343751
? 312502
? 328126
? 335938
? 339844
? 341797
? 342774
? 341798
? 342286
? 341799
? 342042
? 342164
? 342043
? 342103
? 342133
? 342148
? 342156
? 342149
? 342152
? 342154
! 342153

result:

ok Correct position at 342153

Test #35:

score: 0
Accepted
time: 4ms
memory: 3556kb

input:

999999
1
2
1
2
3
2
3
4
3
4
3
4
5
4
5
4
5
6
5
6
7
6
7
6
7
8
9
8
9
9

output:

? 1
? 500000
? 750000
? 500001
? 625000
? 687500
? 625001
? 656250
? 671875
? 656251
? 664063
? 656252
? 660157
? 662110
? 660158
? 661134
? 660159
? 660646
? 660890
? 660647
? 660768
? 660829
? 660769
? 660799
? 660770
? 660784
? 660791
? 660795
? 660792
? 660793
! 660793

result:

ok Correct position at 660793

Test #36:

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

input:

999998
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
2
3
4
5
6
7
8
7
8
7
8
7
8
7
7

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7818
? 11724
? 7819
? 9771
? 10747
? 11235
? 11479
? 11601
? 11662
? 11693
? 11663
? 11678
? 11664
? 11671
? 11665
? 11668
? 11666
! 11666

result:

ok Correct position at 11666

Test #37:

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

input:

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

output:

? 1
? 499999
? 749998
? 874998
? 749999
? 812498
? 843748
? 812499
? 828123
? 835935
? 839841
? 841794
? 842771
? 841795
? 842283
? 841796
? 842039
? 842161
? 842040
? 842100
? 842130
? 842145
? 842153
? 842146
? 842149
? 842151
! 842150

result:

ok Correct position at 842150

Test #38:

score: 0
Accepted
time: 3ms
memory: 3548kb

input:

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

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999939
? 999970
? 999985
? 999993
? 999997
? 999999
! 1000000

result:

ok Correct position at 1000000

Test #39:

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

input:

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

output:

? 1
? 500000
? 750000
? 875000
? 937500
? 968750
? 984375
? 992187
? 996093
? 998046
? 999023
? 999511
? 999755
? 999877
? 999938
? 999969
? 999984
? 999992
? 999996
? 999998
! 999999

result:

ok Correct position at 999999

Test #40:

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

input:

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

output:

? 1
? 500000
? 749999
? 874999
? 937499
? 968749
? 984374
? 992186
? 996092
? 998045
? 999022
? 999510
? 999754
? 999876
? 999937
? 999968
? 999983
? 999991
? 999995
? 999997
! 999998

result:

ok Correct position at 999998

Test #41:

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

input:

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

output:

? 1
? 499999
? 749998
? 874998
? 937498
? 968748
? 984373
? 992185
? 996091
? 998044
? 999021
? 999509
? 999753
? 999875
? 999936
? 999967
? 999982
? 999990
? 999994
? 999996
! 999997

result:

ok Correct position at 999997

Test #42:

score: 0
Accepted
time: 3ms
memory: 3560kb

input:

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

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999939
? 999970
? 999985
? 999993
? 999997
? 999999
! 1000000

result:

ok Correct position at 1000000

Test #43:

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

input:

1000000
0

output:

? 1
! 1

result:

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

Server Time: 2024-12-02 15:32:49 | OpenSource Project