QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#605169#6394. Turn on the Lightlqh2024#AC ✓2ms3864kbC++171.8kb2024-10-02 15:55:182024-10-02 15:55:18

Judging History

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

  • [2024-10-02 15:55:18]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3864kb
  • [2024-10-02 15:55:18]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using i64 = long long;
mt19937_64 rd(time(0));
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K> using rb_tree = tree<K, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class ... A> void debug(const T & t, const A & ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }
const i64 mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);

void QAQ() {
    int n;
    cin >> n;

    int l = 1, r = n;

    auto query = [&](int x) {
        cout << "? " << x << endl;
        cin >> x;
        return x;
    };
    auto print = [&](int x) {
        cout << "! " << x << endl;
        return -1;
    };
    int lst = 0, now = 0;

    while (l < r) {
        int m = l + r >> 1;
        auto chk = [&](int m) {
            now = query(m);
            int tmp = now;
            if (now == abs(lst)) {
                return print(m);
            }
            now = query(r);
            if (now == tmp) {
                return print(r);
            } else if (now == lst) {
                r--;
                l = m + 1;
                lst = now;
            } else {
                lst = now;
                r = m - 1;
            }
            return 0;
        };
        if (chk(m) == -1) {
            return;
        }
    }

    print(l);
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    for (cout << fixed << setprecision(12); t--; QAQ());
}

详细

Test #1:

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

input:

3
1
1

output:

? 2
? 3
! 3

result:

ok Correct position at 3

Test #2:

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

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: 3864kb

input:

9
1
2
1
1

output:

? 5
? 9
? 2
? 4
! 4

result:

ok Correct position at 4

Test #4:

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

input:

8
1
0
1
1

output:

? 4
? 8
? 6
? 7
! 7

result:

ok Correct position at 7

Test #5:

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

input:

7
1
2
3
4

output:

? 4
? 7
? 2
? 3
! 1

result:

ok Correct position at 1

Test #6:

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

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: 3712kb

input:

5
1
2
2

output:

? 3
? 5
? 1
! 1

result:

ok Correct position at 1

Test #8:

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

input:

4
1
1

output:

? 2
? 4
! 4

result:

ok Correct position at 4

Test #9:

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

input:

3
1
1

output:

? 2
? 3
! 3

result:

ok Correct position at 3

Test #10:

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

input:

2
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #11:

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

input:

1

output:

! 1

result:

ok Correct position at 1

Test #12:

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

input:

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

output:

? 500000
? 1000000
? 750000
? 999999
? 625000
? 749999
? 562500
? 624999
? 593749
? 624998
? 609373
? 624997
? 617185
? 624996
? 613279
? 617184
? 615231
? 617183
? 616207
? 617182
? 615719
? 616206
? 615962
? 616205
? 616083
? 616204
? 616143
? 616203
? 616173
? 616202
? 616158
? 616172
? 616150
? ...

result:

ok Correct position at 616155

Test #13:

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

input:

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

output:

? 500000
? 999999
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 93749
? 124998
? 109373
? 124997
? 117185
? 124996
? 113279
? 117184
? 115231
? 117183
? 116207
? 117182
? 115719
? 116206
? 115962
? 116205
? 116083
? 116204
? 116143
? 116203
? 116173
? 116202
? 116158
? 116172
? 116150
? 116...

result:

ok Correct position at 116155

Test #14:

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

input:

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

output:

? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 953120
? 968744
? 960932
? 968743
? 957026
? 960931
? 958978
? 960930
? 959954
? 960929
? 959466
? 959953
? 959709
? 959952
? 959830
? 959951
? 959890
? 959950
? 959920
? 959949
? 959905
? 959919
? 959897
? 9...

result:

ok Correct position at 959902

Test #15:

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

input:

999997
1
2
1
2
1
2
1
2
1
2
1
2
3
4
3
4
3
4
5
6
5
6
5
6
5
6
5
6
7
8
9
10
9
10
9
10
9
9

output:

? 499999
? 999997
? 249999
? 499998
? 374998
? 499997
? 437497
? 499996
? 468746
? 499995
? 484370
? 499994
? 492182
? 499993
? 488276
? 492181
? 490228
? 492180
? 491204
? 492179
? 490716
? 491203
? 490959
? 491202
? 491080
? 491201
? 491140
? 491200
? 491170
? 491199
? 491155
? 491169
? 491147
? 4...

result:

ok Correct position at 491152

Test #16:

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

input:

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

output:

? 499998
? 999996
? 749997
? 999995
? 624997
? 749996
? 687496
? 749995
? 718745
? 749994
? 734369
? 749993
? 742181
? 749992
? 738275
? 742180
? 740227
? 742179
? 741203
? 742178
? 740715
? 741202
? 740958
? 741201
? 741079
? 741200
? 741139
? 741199
? 741169
? 741198
? 741154
? 741168
? 741146
? 7...

result:

ok Correct position at 741151

Test #17:

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

input:

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

output:

? 499998
? 999995
? 249999
? 499997
? 124999
? 249998
? 187498
? 249997
? 218747
? 249996
? 234371
? 249995
? 242183
? 249994
? 238277
? 242182
? 240229
? 242181
? 241205
? 242180
? 240717
? 241204
? 240960
? 241203
? 241081
? 241202
? 241141
? 241201
? 241171
? 241200
? 241156
? 241170
? 241148
? 2...

result:

ok Correct position at 241153

Test #18:

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

input:

999994
1
0
1
0
1
2
1
2
1
2
1
2
3
4
3
4
3
4
5
6
5
6
5
6
5
6
5
6
7
8
9
10
9
10
9
10
9
9

output:

? 499997
? 999994
? 749995
? 999993
? 874994
? 999992
? 812494
? 874993
? 843743
? 874992
? 859367
? 874991
? 867179
? 874990
? 863273
? 867178
? 865225
? 867177
? 866201
? 867176
? 865713
? 866200
? 865956
? 866199
? 866077
? 866198
? 866137
? 866197
? 866167
? 866196
? 866152
? 866166
? 866144
? 8...

result:

ok Correct position at 866149

Test #19:

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

input:

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

output:

? 499997
? 999993
? 249998
? 499996
? 374997
? 499995
? 312497
? 374996
? 343746
? 374995
? 359370
? 374994
? 367182
? 374993
? 363276
? 367181
? 365228
? 367180
? 366204
? 367179
? 365716
? 366203
? 365959
? 366202
? 366080
? 366201
? 366140
? 366200
? 366170
? 366199
? 366155
? 366169
? 366147
? 3...

result:

ok Correct position at 366152

Test #20:

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

input:

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

output:

? 499996
? 999992
? 749994
? 999991
? 624995
? 749993
? 562495
? 624994
? 593744
? 624993
? 609368
? 624992
? 617180
? 624991
? 613274
? 617179
? 615226
? 617178
? 616202
? 617177
? 615714
? 616201
? 615957
? 616200
? 616078
? 616199
? 616138
? 616198
? 616168
? 616197
? 616153
? 616167
? 616145
? 6...

result:

ok Correct position at 616150

Test #21:

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

input:

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

output:

? 499996
? 999991
? 249998
? 499995
? 124999
? 249997
? 62499
? 124998
? 93748
? 124997
? 109372
? 124996
? 117184
? 124995
? 113278
? 117183
? 115230
? 117182
? 116206
? 117181
? 115718
? 116205
? 115961
? 116204
? 116082
? 116203
? 116142
? 116202
? 116172
? 116201
? 116157
? 116171
? 116149
? 116...

result:

ok Correct position at 116154

Test #22:

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

input:

1000000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
27
28
29
30
29
30
29
29

output:

? 500000
? 1000000
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 31250
? 62499
? 15625
? 31249
? 7812
? 15624
? 3906
? 7811
? 1953
? 3905
? 976
? 1952
? 488
? 975
? 244
? 487
? 122
? 243
? 61
? 121
? 30
? 60
? 45
? 59
? 37
? 44
? 40
? 43
! 43

result:

ok Correct position at 43

Test #23:

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

input:

999999
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
27
28
27
28
29
30
29
29

output:

? 500000
? 999999
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 31250
? 62499
? 15625
? 31249
? 7812
? 15624
? 3906
? 7811
? 1953
? 3905
? 976
? 1952
? 488
? 975
? 244
? 487
? 122
? 243
? 61
? 121
? 30
? 60
? 45
? 59
? 52
? 58
? 48
? 51
! 51

result:

ok Correct position at 51

Test #24:

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
17
18
19
20
21
22
23
24
25
26
27
28
27
28
27
28
29
30
29
29

output:

? 499999
? 999998
? 249999
? 499998
? 124999
? 249998
? 62499
? 124998
? 31249
? 62498
? 15624
? 31248
? 7812
? 15623
? 3906
? 7811
? 1953
? 3905
? 976
? 1952
? 488
? 975
? 244
? 487
? 122
? 243
? 61
? 121
? 30
? 60
? 45
? 59
? 52
? 58
? 48
? 51
! 51

result:

ok Correct position at 51

Test #25:

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

input:

999997
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
27
28
27
28
29
30
29
29

output:

? 499999
? 999997
? 249999
? 499998
? 124999
? 249998
? 62499
? 124998
? 31249
? 62498
? 15624
? 31248
? 7812
? 15623
? 3906
? 7811
? 1953
? 3905
? 976
? 1952
? 488
? 975
? 244
? 487
? 122
? 243
? 61
? 121
? 30
? 60
? 45
? 59
? 52
? 58
? 48
? 51
! 51

result:

ok Correct position at 51

Test #26:

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

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
4
3
4
5
6
7
8
7
8
7
7

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
? 999866
? 999776
? 999805
? 999790
? 999804
? 999783
? ...

result:

ok Correct position at 999781

Test #27:

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

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: 3800kb

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: 3704kb

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: 3804kb

input:

1000000
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
3
4
5
6
5
6
5
5

output:

? 500000
? 1000000
? 250000
? 499999
? 374999
? 499998
? 437498
? 499997
? 468747
? 499996
? 484371
? 499995
? 492183
? 499994
? 496088
? 499993
? 498040
? 499992
? 499016
? 499991
? 499503
? 499990
? 499746
? 499989
? 499867
? 499988
? 499927
? 499987
? 499957
? 499986
? 499942
? 499956
? 499949
? ...

result:

ok Correct position at 499947

Test #31:

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

input:

999999
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
23
24
25
26
27
28
27
28
29
30
29
29

output:

? 500000
? 999999
? 749999
? 999998
? 624999
? 749998
? 562499
? 624998
? 531249
? 562498
? 515624
? 531248
? 507812
? 515623
? 503906
? 507811
? 501953
? 503905
? 500976
? 501952
? 500488
? 500975
? 500244
? 500487
? 500122
? 500243
? 500061
? 500121
? 500091
? 500120
? 500076
? 500090
? 500068
? 5...

result:

ok Correct position at 500070

Test #32:

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

input:

999998
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
23
24
25
26
25
26
27
28
29
30
30

output:

? 499999
? 999998
? 749998
? 999997
? 624998
? 749997
? 562498
? 624997
? 531248
? 562497
? 515623
? 531247
? 507811
? 515622
? 503905
? 507810
? 501952
? 503904
? 500975
? 501951
? 500487
? 500974
? 500243
? 500486
? 500121
? 500242
? 500060
? 500120
? 500090
? 500119
? 500075
? 500089
? 500082
? 5...

result:

ok Correct position at 500076

Test #33:

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

input:

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

output:

? 499999
? 999997
? 249999
? 499998
? 374998
? 499997
? 437497
? 499996
? 468746
? 499995
? 484370
? 499994
? 492182
? 499993
? 496087
? 499992
? 498039
? 499991
? 499015
? 499990
? 499502
? 499989
? 499745
? 499988
? 499866
? 499987
? 499926
? 499986
? 499956
? 499985
? 499970
? 499984
? 499963
? 4...

result:

ok Correct position at 499965

Test #34:

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

input:

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

output:

? 500000
? 1000000
? 750000
? 999999
? 625000
? 749999
? 687499
? 749998
? 718748
? 749997
? 734372
? 749996
? 742184
? 749995
? 746089
? 749994
? 748041
? 749993
? 749017
? 749992
? 749504
? 749991
? 749747
? 749990
? 749868
? 749989
? 749928
? 749988
? 749958
? 749987
? 749972
? 749986
? 749979
? ...

result:

ok Correct position at 749984

Test #35:

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

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

output:

? 500000
? 999999
? 250000
? 499999
? 374999
? 499998
? 437498
? 499997
? 468747
? 499996
? 484371
? 499995
? 492183
? 499994
? 496088
? 499993
? 498040
? 499992
? 499016
? 499991
? 499503
? 499990
? 499746
? 499989
? 499867
? 499988
? 499927
? 499987
? 499957
? 499986
? 499971
? 499985
? 499978
? 4...

result:

ok Correct position at 499983

Test #36:

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

input:

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

output:

? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 984369
? 999993
? 992181
? 999992
? 988275
? 992180
? 990227
? 992179
? 991203
? 992178
? 991690
? 992177
? 991933
? 992176
? 992054
? 992175
? 992114
? 992174
? 992144
? 992173
? 992158
? 992172
? 992165
? 9...

result:

ok Correct position at 992170

Test #37:

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

input:

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

output:

? 499999
? 999997
? 249999
? 499998
? 374998
? 499997
? 437497
? 499996
? 468746
? 499995
? 484370
? 499994
? 492182
? 499993
? 496087
? 499992
? 498039
? 499991
? 499015
? 499990
? 499502
? 499989
? 499745
? 499988
? 499866
? 499987
? 499926
? 499986
? 499956
? 499985
? 499970
? 499984
? 499977
? 4...

result:

ok Correct position at 499982

Test #38:

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

input:

1000000
1
2
3
4
5
6
7
8
9
10
11
12
11
12
13
14
15
16
15
16
17
18
19
20
21
22
23
24
23
24
25
26
25
26
25
26
26

output:

? 500000
? 1000000
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 31250
? 62499
? 15625
? 31249
? 7812
? 15624
? 11718
? 15623
? 9765
? 11717
? 8788
? 9764
? 9276
? 9763
? 9032
? 9275
? 8910
? 9031
? 8849
? 8909
? 8818
? 8848
? 8833
? 8847
? 8825
? 8832
? 8828
? 8831
? 8829
! 8829

result:

ok Correct position at 8829

Test #39:

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

input:

999999
1
2
3
4
5
6
7
8
9
10
11
12
11
12
13
14
15
16
15
16
17
18
19
20
21
22
23
24
23
24
25
26
25
26
25
26
26

output:

? 500000
? 999999
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 31250
? 62499
? 15625
? 31249
? 7812
? 15624
? 11718
? 15623
? 9765
? 11717
? 8788
? 9764
? 9276
? 9763
? 9032
? 9275
? 8910
? 9031
? 8849
? 8909
? 8818
? 8848
? 8833
? 8847
? 8825
? 8832
? 8828
? 8831
? 8829
! 8829

result:

ok Correct position at 8829

Test #40:

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

input:

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

output:

? 499999
? 999998
? 249999
? 499998
? 374998
? 499997
? 437497
? 499996
? 468746
? 499995
? 484370
? 499994
? 492182
? 499993
? 488276
? 492181
? 486323
? 488275
? 485346
? 486322
? 485834
? 486321
? 485590
? 485833
? 485468
? 485589
? 485407
? 485467
? 485376
? 485406
? 485391
? 485405
? 485383
? 4...

result:

ok Correct position at 485387

Test #41:

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

input:

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

output:

? 499999
? 999997
? 249999
? 499998
? 374998
? 499997
? 437497
? 499996
? 468746
? 499995
? 484370
? 499994
? 492182
? 499993
? 488276
? 492181
? 486323
? 488275
? 485346
? 486322
? 485834
? 486321
? 485590
? 485833
? 485468
? 485589
? 485407
? 485467
? 485376
? 485406
? 485391
? 485405
? 485383
? 4...

result:

ok Correct position at 485387

Test #42:

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

input:

1000000
1
1

output:

? 500000
? 1000000
! 1000000

result:

ok Correct position at 1000000

Test #43:

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

input:

1000000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
36

output:

? 500000
? 1000000
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 31250
? 62499
? 15625
? 31249
? 7812
? 15624
? 3906
? 7811
? 1953
? 3905
? 976
? 1952
? 488
? 975
? 244
? 487
? 122
? 243
? 61
? 121
? 30
? 60
? 15
? 29
? 7
? 14
? 3
? 6
? 1
! 1

result:

ok Correct position at 1