QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378778#6394. Turn on the Lightgogo11#AC ✓1ms3700kbC++171.7kb2024-04-06 14:36:582024-04-06 14:37:00

Judging History

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

  • [2024-04-06 14:37:00]
  • 评测
  • 测评结果：AC
  • 用时：1ms
  • 内存：3700kb
查看
  • [2024-04-06 14:36:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ui = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define lowbit(x) ((x) & (-x))
constexpr int N = 2e5 + 10;
constexpr int M = 5e5 + 10;
constexpr ll mod = (1LL<<20);
constexpr int INF = 0x3f3f3f3f;
constexpr ll Base = 131;
constexpr int MAXBIT = 19;

int query(int x) {
    cout << "? " << x << endl;
    int res;
    cin >> res;
    return res;
}
void print(int ans)
{
    cout << "! " << ans << endl;
}


void solve()
{   
    int n;
    cin >> n;
    int ans = 0;
    int l = 1, r = n;

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

        if(ans == 0)
        {
            ll t = query(mid);
            if(t == ans)
            {
                print(mid);
                return;
            }
            else 
            {
                t = query(l);
                if(t == 1)
                {
                    print(l);
                    return;
                }
                else if(t == 2) l = mid + 1;
                else if(t == 0) ++ l, r = mid - 1;
            }

            ans = t;
            continue;
        }

        
        ll t = query(mid);
        if(t == ans) 
        {
            print(mid);
            return;
        }
        else if(t > ans) l = mid + 1;
        else r = mid - 1;

        ans = t;
    }
}
int main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    int _ = 1;
    // cin >> _;
    while (_--)
        solve();
    return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1
2
2

output:

? 2
? 1
? 3
! 3

result:

ok Correct position at 3

Test #2:

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

input:

10
1
0
1
0
0

output:

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

result:

ok Correct position at 3

Test #3:

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

input:

9
1
2
1
0
0

output:

? 5
? 1
? 8
? 7
? 6
! 6

result:

ok Correct position at 6

Test #4:

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

input:

8
1
0
1
1

output:

? 5
? 1
? 3
? 2
! 2

result:

ok Correct position at 2

Test #5:

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

input:

7
1
2
3
3

output:

? 4
? 1
? 6
? 7
! 7

result:

ok Correct position at 7

Test #6:

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

input:

6
1
0
1
1

output:

? 4
? 1
? 3
? 2
! 2

result:

ok Correct position at 2

Test #7:

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

input:

5
1
2
2

output:

? 3
? 1
? 5
! 5

result:

ok Correct position at 5

Test #8:

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

input:

4
1
1

output:

? 3
? 1
! 1

result:

ok Correct position at 1

Test #9:

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

input:

3
1
1

output:

? 2
? 1
! 1

result:

ok Correct position at 1

Test #10:

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

input:

2
1
1

output:

? 2
? 1
! 1

result:

ok Correct position at 1

Test #11:

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

input:

1
0

output:

? 1
! 1

result:

ok Correct position at 1

Test #12:

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

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:

? 500001
? 1
? 250001
? 2
? 375001
? 437501
? 406251
? 390626
? 382814
? 375002
? 386720
? 384767
? 383791
? 382815
? 384279
? 384035
? 384157
? 384218
? 384249
? 384234
? 384226
? 384222
? 384220
? 384219
! 384219

result:

ok Correct position at 384219

Test #13:

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

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
? 1
? 750000
? 875000
? 812500
? 843750
? 828125
? 820313
? 816407
? 812501
? 818360
? 817384
? 816896
? 816408
? 817140
? 817018
? 817079
? 817110
? 817095
? 817087
? 817083
? 817080
? 817085
! 817085

result:

ok Correct position at 817085

Test #14:

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

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
2

output:

? 500000
? 1
? 250001
? 2
? 125002
? 3
? 62503
? 4
? 31254
? 5
? 46879
? 39067
? 35161
? 31255
? 37114
? 36138
? 35650
? 35162
? 35894
? 36016
? 35955
? 35925
? 35910
? 35895
? 35903
? 35896
? 35907
? 35905
? 35906
! 35906

result:

ok Correct position at 35906

Test #15:

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

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
? 1
? 749999
? 624999
? 562499
? 500000
? 593749
? 578124
? 570312
? 562500
? 574218
? 572265
? 571289
? 570313
? 571777
? 571533
? 571655
? 571716
? 571747
? 571732
? 571724
? 571720
? 571718
? 571717
! 571717

result:

ok Correct position at 571717

Test #16:

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

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
2

output:

? 499999
? 1
? 250000
? 2
? 375000
? 312500
? 281250
? 250001
? 296875
? 289063
? 285157
? 281251
? 283204
? 281252
? 284181
? 283693
? 283449
? 283205
? 283571
? 283632
? 283602
? 283587
? 283579
? 283572
? 283583
? 283581
? 283582
! 283582

result:

ok Correct position at 283582

Test #17:

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

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
? 1
? 749997
? 874997
? 812497
? 843747
? 828122
? 820310
? 816404
? 812498
? 818357
? 817381
? 816893
? 816405
? 817137
? 817015
? 817076
? 817107
? 817092
? 817084
? 817080
? 817077
? 817082
! 817082

result:

ok Correct position at 817082

Test #18:

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

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
2

output:

? 499998
? 1
? 250000
? 2
? 125001
? 3
? 187501
? 156251
? 140626
? 125002
? 148439
? 144533
? 142580
? 140627
? 143557
? 143069
? 142825
? 142581
? 142947
? 143008
? 142978
? 142963
? 142955
? 142948
? 142959
? 142957
? 142958
! 142958

result:

ok Correct position at 142958

Test #19:

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

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
? 1
? 749996
? 624997
? 562497
? 499998
? 593747
? 578122
? 570310
? 562498
? 574216
? 572263
? 571287
? 570311
? 571775
? 571531
? 571653
? 571714
? 571745
? 571730
? 571722
? 571718
? 571716
? 571715
! 571715

result:

ok Correct position at 571715

Test #20:

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

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:

? 499997
? 1
? 249999
? 2
? 374998
? 437498
? 406248
? 390623
? 382811
? 374999
? 386717
? 384764
? 383788
? 382812
? 384276
? 384032
? 384154
? 384215
? 384246
? 384231
? 384223
? 384219
? 384217
? 384216
! 384216

result:

ok Correct position at 384216

Test #21:

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

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
? 1
? 749994
? 874993
? 812494
? 781244
? 765619
? 749995
? 773432
? 769526
? 767573
? 765620
? 766597
? 765621
? 767085
? 766841
? 766963
? 767024
? 767055
? 767040
? 767032
? 767028
? 767026
? 767025
! 767025

result:

ok Correct position at 767025

Test #22:

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

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
4

output:

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

result:

ok Correct position at 43

Test #23:

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

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

output:

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

result:

ok Correct position at 51

Test #24:

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

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

output:

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

result:

ok Correct position at 51

Test #25:

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

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

output:

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

result:

ok Correct position at 51

Test #26:

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

input:

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

output:

? 500001
? 1
? 750001
? 875001
? 937501
? 968751
? 984376
? 992189
? 996095
? 998048
? 999025
? 999513
? 999757
? 999879
? 999818
? 999788
? 999773
? 999781
! 999781

result:

ok Correct position at 999781

Test #27:

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

input:

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

output:

? 500000
? 1
? 750000
? 875000
? 937500
? 968750
? 984375
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999939
? 999970
? 999985
? 999978
? 999982
? 999980
! 999980

result:

ok Correct position at 999980

Test #28:

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

input:

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

output:

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

result:

ok Correct position at 999979

Test #29:

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

input:

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

output:

? 499999
? 1
? 749999
? 874999
? 937499
? 968749
? 984374
? 992186
? 996092
? 998045
? 999022
? 999510
? 999754
? 999876
? 999937
? 999968
? 999983
? 999976
? 999980
? 999978
! 999978

result:

ok Correct position at 999978

Test #30:

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

input:

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

output:

? 500001
? 1
? 250001
? 2
? 375001
? 437501
? 468751
? 484376
? 492189
? 496095
? 498048
? 499025
? 499513
? 499757
? 499879
? 499940
? 499971
? 499956
? 499948
? 499944
? 499946
? 499947
! 499947

result:

ok Correct position at 499947

Test #31:

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

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

output:

? 500000
? 1
? 750000
? 625000
? 562500
? 500001
? 531251
? 500002
? 515627
? 500003
? 507815
? 500004
? 503910
? 500005
? 501958
? 500006
? 500982
? 500007
? 500495
? 500008
? 500252
? 500009
? 500131
? 500010
? 500071
? 500011
? 500041
? 500012
? 500056
? 500064
? 500068
? 500070
! 500070

result:

ok Correct position at 500070

Test #32:

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

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:

? 500000
? 1
? 750000
? 625000
? 562500
? 500001
? 531251
? 500002
? 515627
? 500003
? 507815
? 500004
? 503910
? 500005
? 501958
? 500006
? 500982
? 500007
? 500495
? 500008
? 500252
? 500009
? 500131
? 500010
? 500071
? 500011
? 500101
? 500086
? 500079
? 500072
? 500076
! 500076

result:

ok Correct position at 500076

Test #33:

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

input:

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

output:

? 499999
? 1
? 250000
? 2
? 375000
? 437500
? 468750
? 484375
? 492187
? 496093
? 498046
? 499023
? 499511
? 499755
? 499877
? 499938
? 499969
? 499954
? 499962
? 499966
? 499964
? 499965
! 499965

result:

ok Correct position at 499965

Test #34:

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

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:

? 500001
? 1
? 250001
? 2
? 375001
? 312501
? 281251
? 250002
? 296876
? 289064
? 285158
? 281252
? 283205
? 281253
? 284182
? 283694
? 283450
? 283206
? 283328
? 283207
? 283389
? 283359
? 283344
? 283329
? 283337
? 283330
? 283334
? 283331
? 283333
! 283333

result:

ok Correct position at 283333

Test #35:

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

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
? 1
? 750000
? 625000
? 562500
? 500001
? 593750
? 578125
? 570313
? 562501
? 566407
? 562502
? 568360
? 567384
? 566896
? 566408
? 566652
? 566409
? 566774
? 566713
? 566683
? 566653
? 566668
? 566654
? 566676
? 566672
? 566670
? 566669
! 566669

result:

ok Correct position at 566669

Test #36:

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

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
0

output:

? 500000
? 1
? 250001
? 2
? 125002
? 3
? 62503
? 4
? 31254
? 5
? 15630
? 6
? 7818
? 7
? 11724
? 9771
? 8795
? 7819
? 8307
? 7820
? 8551
? 8429
? 8368
? 8308
? 8399
? 8384
? 8376
? 8369
? 8380
? 8378
? 8377
! 8377

result:

ok Correct position at 8377

Test #37:

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

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
? 1
? 749999
? 624999
? 562499
? 500000
? 593749
? 578124
? 570312
? 562500
? 566406
? 562501
? 568359
? 567383
? 566895
? 566407
? 566651
? 566408
? 566773
? 566712
? 566682
? 566652
? 566667
? 566653
? 566675
? 566671
? 566669
? 566668
! 566668

result:

ok Correct position at 566668

Test #38:

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

input:

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

output:

? 500001
? 1
? 750001
? 875001
? 937501
? 968751
? 984376
? 992189
? 988283
? 986330
? 985353
? 985842
? 985598
? 985476
? 985415
? 985384
? 985400
? 985392
? 985396
? 985398
? 985399
! 985399

result:

ok Correct position at 985399

Test #39:

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

input:

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

output:

? 500000
? 1
? 750000
? 875000
? 937500
? 968750
? 984375
? 992188
? 988282
? 986329
? 985352
? 985841
? 985597
? 985475
? 985414
? 985383
? 985399
? 985391
? 985395
? 985397
? 985398
! 985398

result:

ok Correct position at 985398

Test #40:

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

input:

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

output:

? 500000
? 1
? 750000
? 625000
? 687500
? 718750
? 734375
? 742188
? 738282
? 736329
? 735352
? 735841
? 735597
? 735475
? 735414
? 735353
? 735445
? 735430
? 735422
? 735415
? 735426
? 735428
? 735429
! 735429

result:

ok Correct position at 735429

Test #41:

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

input:

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

output:

? 499999
? 1
? 749999
? 624999
? 687499
? 718749
? 734374
? 742187
? 738281
? 736328
? 735351
? 735840
? 735596
? 735474
? 735413
? 735352
? 735444
? 735429
? 735421
? 735414
? 735425
? 735427
? 735428
! 735428

result:

ok Correct position at 735428

Test #42:

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

input:

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

output:

? 500001
? 1
? 750001
? 875001
? 937501
? 968751
? 984376
? 992189
? 996095
? 998048
? 999025
? 999513
? 999757
? 999879
? 999940
? 999971
? 999986
? 999994
? 999998
? 1000000
! 1000000

result:

ok Correct position at 1000000

Test #43:

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

input:

1000000
1
1

output:

? 500001
? 1
! 1

result:

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

Server Time: 2024-12-03 17:22:00 | OpenSource Project