QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187797#6394. Turn on the Lightrgnerdplayer#AC ✓1ms3600kbC++201.4kb2023-09-24 22:45:312023-09-24 22:45:31

Judging History

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

  • [2023-09-24 22:45:31]
  • 评测
  • 测评结果：AC
  • 用时：1ms
  • 内存：3600kb
查看
  • [2023-09-24 22:45:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    
    auto solve = [&]() {
        int n;
        cin >> n;

        int l = 1, r = n;
        int cl = 0, cr = 0;

        auto query = [&](int i) {
            cout << "? " << i << endl;
            int x;
            cin >> x;
            return x;
        };

        while (l < r) {
            int m = l + r >> 1;

            int x = query(m);

            if (cl != cr) {
                if (x == abs(cl - cr)) {
                    l = r = m;
                } else if (x == abs(cl + 1 - cr)) {
                    l = m + 1;
                    cl++;
                } else {
                    r = m - 1;
                    cr++;
                }
            } else {
                if (x == 0) {
                    l = r = m;
                } else {
                    int y = query(r);
                    if (y == 1) {
                        l = r;
                    } else if (y == 0) {
                        l = m + 1, r--;
                        cl++, cr++;
                    } else {
                        cr += 2;
                        r = m - 1;
                    }
                }
            }
        }

        cout << "! " << l << endl;
    };

    solve();

    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1
1

output:

? 2
? 3
! 3

result:

ok Correct position at 3

Test #2:

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

input:

10
1
0
1
0

output:

? 5
? 10
? 7
? 9
! 8

result:

ok Correct position at 8

Test #3:

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

input:

9
1
2
1
0

output:

? 5
? 9
? 2
? 3
! 4

result:

ok Correct position at 4

Test #4:

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

input:

8
1
0
1
1

output:

? 4
? 8
? 6
? 7
! 7

result:

ok Correct position at 7

Test #5:

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

input:

7
1
2
3

output:

? 4
? 7
? 2
! 1

result:

ok Correct position at 1

Test #6:

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

input:

6
1
0
1
1

output:

? 3
? 6
? 4
? 5
! 5

result:

ok Correct position at 5

Test #7:

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

input:

5
1
2
2

output:

? 3
? 5
? 1
! 1

result:

ok Correct position at 1

Test #8:

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

input:

4
1
1

output:

? 2
? 4
! 4

result:

ok Correct position at 4

Test #9:

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

input:

3
1
1

output:

? 2
? 3
! 3

result:

ok Correct position at 3

Test #10:

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

input:

2
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #11:

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

input:

1

output:

! 1

result:

ok Correct position at 1

Test #12:

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

input:

1000000
1
0
1
2
3
2
1
0
1
2
1
0
1
2
1
2
3
4
3
2
1
0
1
1

output:

? 500000
? 1000000
? 750000
? 999999
? 625000
? 562500
? 593750
? 609375
? 617187
? 624999
? 613281
? 615234
? 616210
? 617186
? 615722
? 615966
? 615844
? 615783
? 615752
? 615767
? 615775
? 615779
? 615781
? 615782
! 615782

result:

ok Correct position at 615782

Test #13:

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

input:

999999
1
2
3
2
3
2
1
0
1
2
1
0
1
2
1
2
3
2
1
0
1
2
2

output:

? 500000
? 999999
? 250000
? 125000
? 187500
? 156250
? 171875
? 179687
? 183593
? 187499
? 181640
? 182616
? 183104
? 183592
? 182860
? 182982
? 182921
? 182890
? 182905
? 182913
? 182917
? 182920
? 182915
! 182915

result:

ok Correct position at 182915

Test #14:

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

input:

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

output:

? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 953120
? 960932
? 964838
? 968744
? 962885
? 963861
? 964349
? 964837
? 964105
? 963983
? 964044
? 964074
? 964089
? 964104
? 964096
? 964103
? 964092
? 964094
! 964093

result:

ok Correct position at 964093

Test #15:

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

input:

999997
1
2
1
0
1
2
1
0
1
2
1
0
1
2
1
2
3
4
3
2
1
0
1
1

output:

? 499999
? 999997
? 249999
? 374999
? 437499
? 499998
? 406249
? 421874
? 429686
? 437498
? 425780
? 427733
? 428709
? 429685
? 428221
? 428465
? 428343
? 428282
? 428251
? 428266
? 428274
? 428278
? 428280
? 428281
! 428281

result:

ok Correct position at 428281

Test #16:

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

input:

999996
1
0
1
2
1
0
1
2
1
0
1
0
1
2
1
0
1
2
3
2
1
0
1
2
1
2

output:

? 499998
? 999996
? 749997
? 999995
? 624997
? 687497
? 718747
? 749996
? 703122
? 710934
? 714840
? 718746
? 716793
? 718745
? 715816
? 716304
? 716548
? 716792
? 716426
? 716365
? 716395
? 716410
? 716418
? 716425
? 716414
? 716416
! 716415

result:

ok Correct position at 716415

Test #17:

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

input:

999995
1
2
3
2
3
2
1
0
1
2
1
0
1
2
1
2
3
2
1
0
1
2
2

output:

? 499998
? 999995
? 249999
? 124999
? 187499
? 156249
? 171874
? 179686
? 183592
? 187498
? 181639
? 182615
? 183103
? 183591
? 182859
? 182981
? 182920
? 182889
? 182904
? 182912
? 182916
? 182919
? 182914
! 182914

result:

ok Correct position at 182914

Test #18:

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

input:

999994
1
0
1
0
1
2
1
0
1
2
1
0
1
2
1
0
1
2
3
2
1
0
1
2
1
2

output:

? 499997
? 999994
? 749995
? 999993
? 874994
? 999992
? 812494
? 843744
? 859369
? 874993
? 851556
? 855462
? 857415
? 859368
? 856438
? 856926
? 857170
? 857414
? 857048
? 856987
? 857017
? 857032
? 857040
? 857047
? 857036
? 857038
! 857037

result:

ok Correct position at 857037

Test #19:

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

input:

999993
1
2
1
0
1
2
1
0
1
2
1
0
1
2
1
2
3
4
3
2
1
0
1
1

output:

? 499997
? 999993
? 249998
? 374997
? 437497
? 499996
? 406247
? 421872
? 429684
? 437496
? 425778
? 427731
? 428707
? 429683
? 428219
? 428463
? 428341
? 428280
? 428249
? 428264
? 428272
? 428276
? 428278
? 428279
! 428279

result:

ok Correct position at 428279

Test #20:

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

input:

999992
1
0
1
2
3
2
1
0
1
2
1
0
1
2
1
2
3
4
3
2
1
0
1
1

output:

? 499996
? 999992
? 749994
? 999991
? 624995
? 562495
? 593745
? 609370
? 617182
? 624994
? 613276
? 615229
? 616205
? 617181
? 615717
? 615961
? 615839
? 615778
? 615747
? 615762
? 615770
? 615774
? 615776
? 615777
! 615777

result:

ok Correct position at 615777

Test #21:

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

input:

999991
1
2
3
2
1
0
1
2
1
0
1
0
1
2
1
2
3
4
3
2
1
0
1
1

output:

? 499996
? 999991
? 249998
? 124999
? 187498
? 218748
? 234373
? 249997
? 226560
? 230466
? 232419
? 234372
? 233395
? 234371
? 232907
? 233151
? 233029
? 232968
? 232937
? 232952
? 232960
? 232964
? 232966
? 232967
! 232967

result:

ok Correct position at 232967

Test #22:

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

input:

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

output:

? 500000
? 1000000
? 250000
? 125000
? 62500
? 31250
? 15625
? 7812
? 3906
? 1953
? 976
? 488
? 244
? 122
? 61
? 30
? 45
? 37
? 41
? 43
! 43

result:

ok Correct position at 43

Test #23:

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

input:

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

output:

? 500000
? 999999
? 250000
? 125000
? 62500
? 31250
? 15625
? 7812
? 3906
? 1953
? 976
? 488
? 244
? 122
? 61
? 30
? 45
? 53
? 49
? 51
! 51

result:

ok Correct position at 51

Test #24:

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

input:

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

output:

? 499999
? 999998
? 249999
? 124999
? 62499
? 31249
? 15624
? 7812
? 3906
? 1953
? 976
? 488
? 244
? 122
? 61
? 30
? 45
? 53
? 49
? 51
! 51

result:

ok Correct position at 51

Test #25:

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

input:

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

output:

? 499999
? 999997
? 249999
? 124999
? 62499
? 31249
? 15624
? 7812
? 3906
? 1953
? 976
? 488
? 244
? 122
? 61
? 30
? 45
? 53
? 49
? 51
! 51

result:

ok Correct position at 51

Test #26:

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

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

output:

? 500000
? 1000000
? 750000
? 999999
? 874999
? 999998
? 937498
? 999997
? 968747
? 999996
? 984371
? 999995
? 992183
? 999994
? 996088
? 999993
? 998040
? 999992
? 999016
? 999991
? 999503
? 999990
? 999746
? 999989
? 999867
? 999988
? 999806
? 999776
? 999791
? 999783
? 999779
? 999781
! 999781

result:

ok Correct position at 999781

Test #27:

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

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
0

output:

? 500000
? 999999
? 749999
? 999998
? 874998
? 999997
? 937497
? 999996
? 968746
? 999995
? 984370
? 999994
? 992182
? 999993
? 996087
? 999992
? 998039
? 999991
? 999015
? 999990
? 999502
? 999989
? 999745
? 999988
? 999866
? 999987
? 999926
? 999986
? 999956
? 999985
? 999970
? 999984
? 999977
? 9...

result:

ok Correct position at 999980

Test #28:

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

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
0

output:

? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 984369
? 999993
? 992181
? 999992
? 996086
? 999991
? 998038
? 999990
? 999014
? 999989
? 999501
? 999988
? 999744
? 999987
? 999865
? 999986
? 999925
? 999985
? 999955
? 999984
? 999969
? 999983
? 999976
? 9...

result:

ok Correct position at 999979

Test #29:

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

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
0

output:

? 499999
? 999997
? 749998
? 999996
? 874997
? 999995
? 937496
? 999994
? 968745
? 999993
? 984369
? 999992
? 992180
? 999991
? 996085
? 999990
? 998037
? 999989
? 999013
? 999988
? 999500
? 999987
? 999743
? 999986
? 999864
? 999985
? 999924
? 999984
? 999954
? 999983
? 999968
? 999982
? 999975
? 9...

result:

ok Correct position at 999978

Test #30:

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

input:

1000000
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
1
2
2

output:

? 500000
? 1000000
? 250000
? 375000
? 437500
? 499999
? 468749
? 499998
? 484373
? 499997
? 492185
? 499996
? 496090
? 499995
? 498042
? 499994
? 499018
? 499993
? 499505
? 499992
? 499748
? 499991
? 499869
? 499990
? 499929
? 499989
? 499959
? 499988
? 499944
? 499951
? 499947
! 499947

result:

ok Correct position at 499947

Test #31:

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

input:

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

output:

? 500000
? 999999
? 749999
? 999998
? 624999
? 562499
? 531249
? 515624
? 507812
? 503906
? 501953
? 500976
? 500488
? 500244
? 500122
? 500061
? 500091
? 500076
? 500068
? 500072
? 500070
! 500070

result:

ok Correct position at 500070

Test #32:

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

input:

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

output:

? 499999
? 999998
? 749998
? 999997
? 624998
? 562498
? 531248
? 515623
? 507811
? 503905
? 501952
? 500975
? 500487
? 500243
? 500121
? 500060
? 500090
? 500075
? 500082
? 500078
? 500076
! 500076

result:

ok Correct position at 500076

Test #33:

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

input:

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

output:

? 499999
? 999997
? 249999
? 374999
? 437499
? 499998
? 468748
? 499997
? 484372
? 499996
? 492184
? 499995
? 496089
? 499994
? 498041
? 499993
? 499017
? 499992
? 499504
? 499991
? 499747
? 499990
? 499868
? 499989
? 499928
? 499988
? 499958
? 499987
? 499972
? 499986
? 499965
! 499965

result:

ok Correct position at 499965

Test #34:

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

input:

1000000
1
0
1
2
1
0
1
2
1
0
1
0
1
2
1
0
1
0
1
2
1
0
1
0
1
0
1
0
0

output:

? 500000
? 1000000
? 750000
? 999999
? 625000
? 687500
? 718750
? 749999
? 703125
? 710937
? 714843
? 718749
? 716796
? 718748
? 715819
? 716307
? 716551
? 716795
? 716673
? 716794
? 716612
? 716642
? 716657
? 716672
? 716664
? 716671
? 716667
? 716670
? 716668
! 716668

result:

ok Correct position at 716668

Test #35:

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

input:

999999
1
2
1
0
1
2
1
0
1
0
1
2
1
0
1
0
1
2
1
0
1
0
1
2
1
0
1
1

output:

? 500000
? 999999
? 250000
? 375000
? 437500
? 499999
? 406250
? 421875
? 429687
? 437499
? 433593
? 437498
? 431640
? 432616
? 433104
? 433592
? 433348
? 433591
? 433226
? 433287
? 433317
? 433347
? 433332
? 433346
? 433324
? 433328
? 433330
? 433331
! 433331

result:

ok Correct position at 433331

Test #36:

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

input:

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

output:

? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 984369
? 999993
? 992181
? 999992
? 988275
? 990228
? 991204
? 992180
? 991692
? 992179
? 991448
? 991570
? 991631
? 991691
? 991600
? 991615
? 991623
? 991630
? 991619
? 991621
! 991622

result:

ok Correct position at 991622

Test #37:

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

input:

999997
1
2
1
0
1
2
1
0
1
0
1
2
1
0
1
0
1
2
1
0
1
0
1
2
1
0
1
1

output:

? 499999
? 999997
? 249999
? 374999
? 437499
? 499998
? 406249
? 421874
? 429686
? 437498
? 433592
? 437497
? 431639
? 432615
? 433103
? 433591
? 433347
? 433590
? 433225
? 433286
? 433316
? 433346
? 433331
? 433345
? 433323
? 433327
? 433329
? 433330
! 433330

result:

ok Correct position at 433330

Test #38:

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

input:

1000000
1
2
3
4
5
6
7
6
5
4
5
4
3
2
1
2
1
2
3
4

output:

? 500000
? 1000000
? 250000
? 125000
? 62500
? 31250
? 15625
? 7812
? 11718
? 13671
? 14648
? 14159
? 14403
? 14525
? 14586
? 14617
? 14601
? 14609
? 14605
? 14603
! 14602

result:

ok Correct position at 14602

Test #39:

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

input:

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

output:

? 500000
? 999999
? 250000
? 125000
? 62500
? 31250
? 15625
? 7812
? 11718
? 13671
? 14648
? 14159
? 14403
? 14525
? 14586
? 14617
? 14601
? 14609
? 14605
? 14603
! 14602

result:

ok Correct position at 14602

Test #40:

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

input:

999998
1
2
1
2
3
4
5
4
3
2
3
2
1
0
1
2
1
0
1
2
3
4

output:

? 499999
? 999998
? 249999
? 374999
? 312499
? 281249
? 265624
? 257811
? 261717
? 263670
? 264647
? 264158
? 264402
? 264524
? 264585
? 264646
? 264554
? 264569
? 264577
? 264584
? 264573
? 264571
! 264570

result:

ok Correct position at 264570

Test #41:

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

input:

999997
1
2
1
2
3
4
5
4
3
2
3
2
1
0
1
2
1
0
1
2
3
4

output:

? 499999
? 999997
? 249999
? 374999
? 312499
? 281249
? 265624
? 257811
? 261717
? 263670
? 264647
? 264158
? 264402
? 264524
? 264585
? 264646
? 264554
? 264569
? 264577
? 264584
? 264573
? 264571
! 264570

result:

ok Correct position at 264570

Test #42:

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

input:

1000000
1
1

output:

? 500000
? 1000000
! 1000000

result:

ok Correct position at 1000000

Test #43:

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

input:

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

output:

? 500000
? 1000000
? 250000
? 125000
? 62500
? 31250
? 15625
? 7812
? 3906
? 1953
? 976
? 488
? 244
? 122
? 61
? 30
? 15
? 7
? 3
? 1
! 1

result:

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

Server Time: 2024-12-02 16:00:11 | OpenSource Project