QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103746#6394. Turn on the LightrniyaAC ✓5ms3508kbC++171.9kb2023-05-07 14:12:472023-05-07 14:12:51

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-07 14:12:51]
  • 评测
  • 测评结果:AC
  • 用时:5ms
  • 内存:3508kb
  • [2023-05-07 14:12:47]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

int n;

int query(int x) {
    assert(0 <= x and x < n);
    cout << "? " << x + 1 << endl;
    int res;
    cin >> res;
    return res;
}

void answer(int x) {
    assert(0 <= x and x < n);
    cout << "! " << x + 1 << endl;
    exit(0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    int lb = 0, ub = n, L = 0, R = 0, res;
    while (ub - lb > 1) {
        int mid = (lb + ub) >> 1;
        res = query(mid);
        if (res == abs(L - R)) answer(mid);
        if (mid == ub - 1) answer(lb);
        res = query(ub - 1);
        if (res == abs(L + 1 - R)) answer(ub - 1);
        if (res == abs(L - (R + 2))) {
            ub = mid;
            R += 2;
        } else {
            assert(res == abs(L - R));
            lb = mid + 1;
            ub--;
            L++, R++;
        }
    }
    answer(lb);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1
1

output:

? 2
? 3
! 3

result:

ok Correct position at 3

Test #2:

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

input:

10
1
2
3
4
5

output:

? 6
? 10
? 3
? 5
? 2
! 1

result:

ok Correct position at 1

Test #3:

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

input:

9
1
2
3
4
5

output:

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

result:

ok Correct position at 1

Test #4:

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

input:

8
1
2
3
4
5

output:

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

result:

ok Correct position at 1

Test #5:

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

input:

7
1
2
3
4

output:

? 4
? 7
? 2
? 3
! 1

result:

ok Correct position at 1

Test #6:

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

input:

6
1
2
3
4

output:

? 4
? 6
? 2
? 3
! 1

result:

ok Correct position at 1

Test #7:

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

input:

5
1
2
3

output:

? 3
? 5
? 2
! 1

result:

ok Correct position at 1

Test #8:

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

input:

4
1
2
3

output:

? 3
? 4
? 2
! 1

result:

ok Correct position at 1

Test #9:

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

input:

3
1
1

output:

? 2
? 3
! 3

result:

ok Correct position at 3

Test #10:

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

input:

2
1

output:

? 2
! 1

result:

ok Correct position at 1

Test #11:

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

input:

1

output:

! 1

result:

ok Correct position at 1

Test #12:

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

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
31
32
33
34
35
36

output:

? 500001
? 1000000
? 250001
? 500000
? 125001
? 250000
? 62501
? 125000
? 31251
? 62500
? 15626
? 31250
? 7813
? 15625
? 3907
? 7812
? 1954
? 3906
? 977
? 1953
? 489
? 976
? 245
? 488
? 123
? 244
? 62
? 122
? 31
? 61
? 16
? 30
? 8
? 15
? 12
? 14
? 10
? 11
! 9

result:

ok Correct position at 9

Test #13:

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

input:

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

output:

? 500000
? 999999
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 93750
? 124998
? 78125
? 93749
? 85937
? 93748
? 82031
? 85936
? 83984
? 85935
? 83008
? 83983
? 82520
? 83007
? 82276
? 82519
? 82154
? 82275
? 82093
? 82153
? 82062
? 82092
? 82047
? 82061
? 82039
? 82046
? 82043
? 82045
? 82...

result:

ok Correct position at 82040

Test #14:

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

input:

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

output:

? 500000
? 999998
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 93750
? 124998
? 78125
? 93749
? 85937
? 93748
? 82031
? 85936
? 83984
? 85935
? 83008
? 83983
? 82520
? 83007
? 82276
? 82519
? 82154
? 82275
? 82093
? 82153
? 82062
? 82092
? 82047
? 82061
? 82039
? 82046
? 82043
? 82045
? 82...

result:

ok Correct position at 82040

Test #15:

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

input:

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

output:

? 499999
? 999997
? 250000
? 499998
? 125000
? 249999
? 62500
? 124999
? 93750
? 124998
? 78125
? 93749
? 85937
? 93748
? 82031
? 85936
? 83984
? 85935
? 83008
? 83983
? 82520
? 83007
? 82276
? 82519
? 82154
? 82275
? 82093
? 82153
? 82062
? 82092
? 82047
? 82061
? 82039
? 82046
? 82043
? 82045
? 82...

result:

ok Correct position at 82040

Test #16:

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

input:

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

output:

? 499999
? 999996
? 250000
? 499998
? 125000
? 249999
? 62500
? 124999
? 93750
? 124998
? 78125
? 93749
? 85937
? 93748
? 82031
? 85936
? 83984
? 85935
? 83008
? 83983
? 82520
? 83007
? 82276
? 82519
? 82154
? 82275
? 82093
? 82153
? 82062
? 82092
? 82047
? 82061
? 82039
? 82046
? 82043
? 82045
? 82...

result:

ok Correct position at 82040

Test #17:

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

input:

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

output:

? 499998
? 999995
? 249999
? 499997
? 125000
? 249998
? 62500
? 124999
? 93750
? 124998
? 78125
? 93749
? 85937
? 93748
? 82031
? 85936
? 83984
? 85935
? 83008
? 83983
? 82520
? 83007
? 82276
? 82519
? 82154
? 82275
? 82093
? 82153
? 82062
? 82092
? 82047
? 82061
? 82039
? 82046
? 82043
? 82045
? 82...

result:

ok Correct position at 82040

Test #18:

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

input:

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

output:

? 499998
? 999994
? 249999
? 499997
? 125000
? 249998
? 62500
? 124999
? 93750
? 124998
? 78125
? 93749
? 85937
? 93748
? 82031
? 85936
? 83984
? 85935
? 83008
? 83983
? 82520
? 83007
? 82276
? 82519
? 82154
? 82275
? 82093
? 82153
? 82062
? 82092
? 82047
? 82061
? 82039
? 82046
? 82043
? 82045
? 82...

result:

ok Correct position at 82040

Test #19:

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

input:

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

output:

? 499997
? 999993
? 249999
? 499996
? 125000
? 249998
? 62500
? 124999
? 93750
? 124998
? 78125
? 93749
? 85937
? 93748
? 82031
? 85936
? 83984
? 85935
? 83008
? 83983
? 82520
? 83007
? 82276
? 82519
? 82154
? 82275
? 82093
? 82153
? 82062
? 82092
? 82047
? 82061
? 82039
? 82046
? 82043
? 82045
? 82...

result:

ok Correct position at 82040

Test #20:

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

input:

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

output:

? 499997
? 999992
? 249999
? 499996
? 125000
? 249998
? 62500
? 124999
? 93750
? 124998
? 78125
? 93749
? 85937
? 93748
? 82031
? 85936
? 83984
? 85935
? 83008
? 83983
? 82520
? 83007
? 82276
? 82519
? 82154
? 82275
? 82093
? 82153
? 82062
? 82092
? 82047
? 82061
? 82039
? 82046
? 82043
? 82045
? 82...

result:

ok Correct position at 82040

Test #21:

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

input:

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

output:

? 499996
? 999991
? 249998
? 499995
? 124999
? 249997
? 62500
? 124998
? 31250
? 62499
? 46875
? 62498
? 39063
? 46874
? 35157
? 39062
? 33204
? 35156
? 32227
? 33203
? 31739
? 32226
? 31495
? 31738
? 31373
? 31494
? 31312
? 31372
? 31281
? 31311
? 31266
? 31280
? 31258
? 31265
? 31262
? 31264
? 312...

result:

ok Correct position at 31259

Test #22:

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

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
30

output:

? 500001
? 1000000
? 250001
? 500000
? 125001
? 250000
? 62501
? 125000
? 31251
? 62500
? 15626
? 31250
? 7813
? 15625
? 3907
? 7812
? 1954
? 3906
? 977
? 1953
? 489
? 976
? 245
? 488
? 123
? 244
? 62
? 122
? 31
? 61
? 46
? 60
? 39
? 45
? 42
? 44
! 43

result:

ok Correct position at 43

Test #23:

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

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
30

output:

? 500000
? 999999
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 31250
? 62499
? 15625
? 31249
? 7813
? 15624
? 3907
? 7812
? 1954
? 3906
? 977
? 1953
? 489
? 976
? 245
? 488
? 123
? 244
? 62
? 122
? 31
? 61
? 46
? 60
? 53
? 59
? 50
? 52
! 51

result:

ok Correct position at 51

Test #24:

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

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
30

output:

? 500000
? 999998
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 31250
? 62499
? 15625
? 31249
? 7813
? 15624
? 3907
? 7812
? 1954
? 3906
? 977
? 1953
? 489
? 976
? 245
? 488
? 123
? 244
? 62
? 122
? 31
? 61
? 46
? 60
? 53
? 59
? 50
? 52
! 51

result:

ok Correct position at 51

Test #25:

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

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
30

output:

? 499999
? 999997
? 250000
? 499998
? 125000
? 249999
? 62500
? 124999
? 31250
? 62499
? 15625
? 31249
? 7813
? 15624
? 3907
? 7812
? 1954
? 3906
? 977
? 1953
? 489
? 976
? 245
? 488
? 123
? 244
? 62
? 122
? 31
? 61
? 46
? 60
? 53
? 59
? 50
? 52
! 51

result:

ok Correct position at 51

Test #26:

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

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
9
10
9
9

output:

? 500001
? 1000000
? 750001
? 999999
? 875000
? 999998
? 937499
? 999997
? 968748
? 999996
? 984372
? 999995
? 992184
? 999994
? 996089
? 999993
? 998041
? 999992
? 999017
? 999991
? 999504
? 999990
? 999747
? 999989
? 999868
? 999988
? 999808
? 999867
? 999778
? 999807
? 999793
? 999806
? 999786
? ...

result:

ok Correct position at 999781

Test #27:

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

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

output:

? 500000
? 999999
? 750000
? 999998
? 874999
? 999997
? 937498
? 999996
? 968747
? 999995
? 984371
? 999994
? 992183
? 999993
? 996088
? 999992
? 998040
? 999991
? 999016
? 999990
? 999503
? 999989
? 999746
? 999988
? 999867
? 999987
? 999927
? 999986
? 999957
? 999985
? 999971
? 999984
? 999978
? 9...

result:

ok Correct position at 999980

Test #28:

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

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

output:

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

result:

ok Correct position at 999979

Test #29:

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

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

output:

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

result:

ok Correct position at 999978

Test #30:

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

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

output:

? 500001
? 1000000
? 250001
? 500000
? 375001
? 499999
? 437500
? 499998
? 468749
? 499997
? 484373
? 499996
? 492185
? 499995
? 496090
? 499994
? 498042
? 499993
? 499018
? 499992
? 499505
? 499991
? 499748
? 499990
? 499869
? 499989
? 499929
? 499988
? 499959
? 499987
? 499944
? 499958
? 499951
? ...

result:

ok Correct position at 499947

Test #31:

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

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
28

output:

? 500000
? 999999
? 750000
? 999998
? 625000
? 749999
? 562500
? 624999
? 531250
? 562499
? 515625
? 531249
? 507813
? 515624
? 503907
? 507812
? 501954
? 503906
? 500977
? 501953
? 500489
? 500976
? 500245
? 500488
? 500123
? 500244
? 500062
? 500122
? 500092
? 500121
? 500077
? 500091
? 500070
! 5...

result:

ok Correct position at 500070

Test #32:

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

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
27
28
27
27

output:

? 500000
? 999998
? 749999
? 999997
? 625000
? 749998
? 562500
? 624999
? 531250
? 562499
? 515625
? 531249
? 507813
? 515624
? 503907
? 507812
? 501954
? 503906
? 500977
? 501953
? 500489
? 500976
? 500245
? 500488
? 500123
? 500244
? 500062
? 500122
? 500092
? 500121
? 500077
? 500091
? 500070
? 5...

result:

ok Correct position at 500076

Test #33:

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

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
7

output:

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

result:

ok Correct position at 499965

Test #34:

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

input:

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

output:

? 500001
? 1000000
? 250001
? 500000
? 125001
? 250000
? 62501
? 125000
? 31251
? 62500
? 15626
? 31250
? 7813
? 15625
? 11719
? 15624
? 13672
? 15623
? 12696
? 13671
? 12208
? 12695
? 11964
? 12207
? 11842
? 11963
? 11781
? 11841
? 11750
? 11780
? 11765
? 11779
? 11772
? 11778
? 11775
? 11777
! 11777

result:

ok Correct position at 11777

Test #35:

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

input:

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

output:

? 500000
? 999999
? 250000
? 499999
? 375000
? 499998
? 312500
? 374999
? 343750
? 374998
? 328125
? 343749
? 335937
? 343748
? 339843
? 343747
? 337890
? 339842
? 338866
? 339841
? 339354
? 339840
? 339110
? 339353
? 339232
? 339352
? 339171
? 339231
? 339201
? 339230
? 339216
? 339229
? 339209
? 3...

result:

ok Correct position at 339207

Test #36:

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

input:

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

output:

? 500000
? 999998
? 250000
? 499999
? 375000
? 499998
? 312500
? 374999
? 343750
? 374998
? 328125
? 343749
? 335937
? 343748
? 339843
? 343747
? 337890
? 339842
? 338866
? 339841
? 339354
? 339840
? 339110
? 339353
? 339232
? 339352
? 339171
? 339231
? 339201
? 339230
? 339216
? 339229
? 339209
? 3...

result:

ok Correct position at 339207

Test #37:

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

input:

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

output:

? 499999
? 999997
? 250000
? 499998
? 125000
? 249999
? 187500
? 249998
? 156250
? 187499
? 171875
? 187498
? 164063
? 171874
? 160157
? 164062
? 158204
? 160156
? 157227
? 158203
? 157715
? 158202
? 157959
? 158201
? 157837
? 157958
? 157898
? 157957
? 157868
? 157897
? 157853
? 157867
? 157845
? 1...

result:

ok Correct position at 157848

Test #38:

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

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
37
38

output:

? 500001
? 1000000
? 250001
? 500000
? 125001
? 250000
? 62501
? 125000
? 31251
? 62500
? 15626
? 31250
? 7813
? 15625
? 3907
? 7812
? 1954
? 3906
? 977
? 1953
? 489
? 976
? 245
? 488
? 123
? 244
? 62
? 122
? 31
? 61
? 16
? 30
? 8
? 15
? 4
? 7
? 2
? 3
! 1

result:

ok Correct position at 1

Test #39:

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

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
29
30
31
32
33
34
35
36
37
38

output:

? 500000
? 999999
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 31250
? 62499
? 15625
? 31249
? 7813
? 15624
? 3907
? 7812
? 1954
? 3906
? 977
? 1953
? 489
? 976
? 245
? 488
? 123
? 244
? 62
? 122
? 31
? 61
? 16
? 30
? 8
? 15
? 4
? 7
? 2
? 3
! 1

result:

ok Correct position at 1

Test #40:

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

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
29
30
31
32
33
34
35
36
37
38

output:

? 500000
? 999998
? 250000
? 499999
? 125000
? 249999
? 62500
? 124999
? 31250
? 62499
? 15625
? 31249
? 7813
? 15624
? 3907
? 7812
? 1954
? 3906
? 977
? 1953
? 489
? 976
? 245
? 488
? 123
? 244
? 62
? 122
? 31
? 61
? 16
? 30
? 8
? 15
? 4
? 7
? 2
? 3
! 1

result:

ok Correct position at 1

Test #41:

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

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
29
30
31
32
33
34
35
36
37
38

output:

? 499999
? 999997
? 250000
? 499998
? 125000
? 249999
? 62500
? 124999
? 31250
? 62499
? 15625
? 31249
? 7813
? 15624
? 3907
? 7812
? 1954
? 3906
? 977
? 1953
? 489
? 976
? 245
? 488
? 123
? 244
? 62
? 122
? 31
? 61
? 16
? 30
? 8
? 15
? 4
? 7
? 2
? 3
! 1

result:

ok Correct position at 1

Test #42:

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

input:

1000000
1
1

output:

? 500001
? 1000000
! 1000000

result:

ok Correct position at 1000000

Test #43:

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

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
37
38

output:

? 500001
? 1000000
? 250001
? 500000
? 125001
? 250000
? 62501
? 125000
? 31251
? 62500
? 15626
? 31250
? 7813
? 15625
? 3907
? 7812
? 1954
? 3906
? 977
? 1953
? 489
? 976
? 245
? 488
? 123
? 244
? 62
? 122
? 31
? 61
? 16
? 30
? 8
? 15
? 4
? 7
? 2
? 3
! 1

result:

ok Correct position at 1