QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#853699#9734. Identify Chorducup-team4435#AC ✓60ms3876kbC++208.0kb2025-01-11 18:23:472025-01-11 18:23:48

Judging History

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

  • [2025-01-11 18:23:48]
  • 评测
  • 测评结果：AC
  • 用时：60ms
  • 内存：3876kb
查看
  • [2025-01-11 18:23:47]
  • 提交

answer

//#pragma GCC optimize("Ofast")

#include "bits/stdc++.h"


#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

int Bit(int mask, int b) { return (mask >> b) & 1; }

template<class T>
bool ckmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool ckmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
    --l;
    while (r - l > 1) {
        T mid = l + (r - l) / 2;
        if (predicat(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}


template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
    return FindFirstTrue(l, r, predicat) - 1;
}

const int INFi = 2e9;
const ll INF = 2e18;


const bool Loc = false;

int Dist(int x, int y, int n) {
    int f = abs(x - y);
    f = min(f, n - f);
    return f;
}

void solve() {
    int n = 1e9; cin >> n;

    pair<int, int> hord;
    if (Loc) {
//        hord = {2, n - 1};
//        cin >> hord.first >> hord.second;
    }

    map<pair<int, int>, int> mem;

    vpi ans;

    int qs = 0;

    auto ask = [&] (int x, int y) {
        if (x == y) return 0;
        if ((x + 1) % n == y || (y + 1) % n == x) return 1;
        x++;
        y++;

        if (Loc) {
            qs++;
            int dist = min({Dist(x, y, n), Dist(x, hord.first, n) + Dist(hord.second, y, n) + 1, Dist(x, hord.second, n) + Dist(hord.first, y, n) + 1});
            if (dist == 1) {
                ans.emplace_back(x, y);
            }
            return dist;
        }

        if (x > y) swap(x, y);
        pi cur = make_pair(x, y);
        if (mem.count(cur)) return mem[cur];
        cout << "? " << x << ' ' << y << endl;
        int ret; cin >> ret;
        mem[cur] = ret;
        if (ret == 1) {
            ans.emplace_back(cur);
        }
        return ret;
    };

    {
        ll cnt = 1ll * n * (n - 1) / 2;
        cnt -= n;

        if (cnt <= 40) {
            for (int i = 2; i < n && ans.empty(); ++i) {
                for (int j = 0; j + 2 <= i && ans.empty(); ++j) {
                    ask(j, i);
                }
            }
            assert(!ans.empty());
            cout << "! " << ans[0].first << ' ' << ans[0].second << endl;
            int ret; cin >> ret;
            if (ret == -1) {
                exit(0);
            }
            return;
        }
    }

    assert(n >= 10);

    if (n % 2 == 0) {
        int mid = n / 2;
        for (int x = 0; x < n && ans.empty(); ++x) {
            assert(x <= 2);

            int y = (x + mid) % n;

            int dist = ask(x, y);
            if (dist == mid) continue;
            if (!ans.empty()) break;

            assert(dist < mid);
            int len = mid - dist + 1;
            assert(len >= 2);

            ask((y + len) % n, y);
            if (!ans.empty()) break;
            ask((y - len + n) % n, y);
            if (!ans.empty()) break;

            if (ask(x, (y + 1) % n) == dist - 1) {
                // down
                if (!ans.empty()) break;

                int L = 1;
                int R = mid - len + 1;
                while (R - L > 1 && ans.empty()) {
                    int M = (L + R) / 2;
                    if (ask(x, (y + M) % n) == dist - M) {
                        L = M;
                    } else {
                        R = M;
                    }
                }
                for(int t = -1; t <= 1 && ans.empty(); t += 2) {
                    int f1 = (y + L) % n;
                    int f2 = (y + 1ll * t * (L + len)) % n;
                    if (f2 < 0) f2 += n;
                    ask(f1, f2);
                }
                assert(!ans.empty());
            } else {
                if (!ans.empty()) break;

                int L = 1;
                int R = mid - len + 1;
                while (R - L > 1 && ans.empty()) {
                    int M = (L + R) / 2;
                    if (ask(x, (y - M + n) % n) == dist - M) {
                        L = M;
                    } else {
                        R = M;
                    }
                }
                for(int t = -1; t <= 1 && ans.empty(); t += 2) {
                    int f1 = (y - L + n) % n;
                    int f2 = (y + 1ll * t * (L + len)) % n;
                    if (f2 < 0) f2 += n;
                    ask(f1, f2);
                }
                assert(!ans.empty());
            }
            break;
        }
    } else {
        int mid = n / 2;
        for (int x = 0; x < n && ans.empty(); ++x) {
            assert(x <= 2);
            int y1 = (x + mid) % n;
            int y2 = (x + mid + 1) % n;

            int dist1 = ask(x, y1);
            if (!ans.empty()) break;
            int dist2 = ask(x, y2);
            if (!ans.empty()) break;

            if (dist1 == dist2) {
                assert(dist1 == mid);
                continue;
            }

            int len = mid - min(dist1, dist2) + 1;
            assert(len >= 2);

            if (dist1 < dist2) {
                int L = 0;
                int R = mid - len + 1;
                while (R - L > 1 && ans.empty()) {
                    int M = (L + R) / 2;
                    if (ask(x, (y1 - M + n) % n) == dist1 - M) {
                        L = M;
                    } else {
                        R = M;
                    }
                }
                if (ans.empty()) {
                    int f1 = (y1 - L + n) % n;
                    int f2 = (y1 - (L + len)) % n;
                    if (f2 < 0) f2 += n;
                    ask(f1, f2);
                }
                if (ans.empty()) {
                    int f1 = (y1 - L + n) % n;
                    int f2 = (y2 + (L + len)) % n;
                    if (f2 < 0) f2 += n;
                    ask(f1, f2);
                }
                assert(!ans.empty());
            }  else {
                int L = 0;
                int R = mid - len + 1;
                while (R - L > 1 && ans.empty()) {
                    int M = (L + R) / 2;
                    if (ask(x, (y2 + M) % n) == dist2 - M) {
                        L = M;
                    } else {
                        R = M;
                    }
                }
                if (ans.empty()) {
                    int f1 = (y2 + L) % n;
                    int f2 = (y1 - (L + len)) % n;
                    if (f2 < 0) f2 += n;
                    ask(f1, f2);
                }
                if (ans.empty()) {
                    int f1 = (y2 + L) % n;
                    int f2 = (y2 + (L + len)) % n;
                    if (f2 < 0) f2 += n;
                    ask(f1, f2);
                }
                assert(!ans.empty());
            }
            break;
        }
    }

    assert(!ans.empty());
    cout << "! " << ans[0].first << ' ' << ans[0].second << endl;

    int ret; cin >> ret;
    if (ret == -1) {
        exit(0);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(12) << fixed;
    int t = 1;

    cin >> t;
    rep(i, t) {
        solve();
    }
    return 0;
}
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
6
2
2
1
1
4
1
1

output:

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

result:

ok ok (2 test cases)

Test #2:

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

input:

1000
15
5
6
5
6
1
1
19
5
4
4
3
1
1
17
5
4
4
3
1
1
15
6
7
3
2
1
1
14
5
3
3
6
2
3
1
1
15
3
2
3
1
1
17
8
8
8
7
4
3
4
1
1
20
6
5
5
7
3
2
1
1
13
5
6
4
4
2
1
1
18
3
3
5
2
3
3
1
1
13
4
3
2
3
3
1
1
14
2
1
1
17
8
7
5
6
6
1
1
12
5
2
2
4
3
3
1
1
10
2
3
2
4
3
2
5
4
3
2
4
5
4
3
2
3
4
3
2
1
1
14
6
2
1
1
19
8
7
4
...

output:

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

result:

ok ok (1000 test cases)

Test #3:

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

input:

1000
21
3
4
2
3
3
1
1
22
8
4
4
7
4
4
3
1
1
20
5
6
1
1
22
10
2
2
9
6
7
7
1
1
21
9
8
6
8
7
1
1
21
8
7
4
5
5
7
1
1
24
11
2
2
11
6
8
8
2
1
1
22
10
2
2
9
6
8
9
4
1
1
21
4
3
2
3
1
1
23
8
7
4
2
3
3
1
1
21
10
10
10
9
6
7
7
1
1
24
9
4
3
8
7
9
9
1
1
20
9
1
1
24
11
2
2
11
6
9
10
1
1
23
8
9
4
2
1
1
23
7
6
3
4
1...

output:

? 1 11
? 1 12
? 1 10
? 1 9
? 2 10
? 10 21
! 10 21
? 1 12
? 12 16
? 8 12
? 1 13
? 1 16
? 1 18
? 1 17
? 3 17
! 3 17
? 1 11
? 11 17
? 5 11
! 5 11
? 1 12
? 12 14
? 10 12
? 1 13
? 1 17
? 1 15
? 1 16
? 7 15
! 7 15
? 1 11
? 1 12
? 1 16
? 1 14
? 1 13
? 7 13
! 7 13
? 1 11
? 1 12
? 1 15
? 1 17
? 1 16
? 4 15
?...

result:

ok ok (1000 test cases)

Test #4:

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

input:

1000
25
8
9
4
2
1
1
25
6
7
3
2
3
3
1
1
25
11
12
6
4
5
4
2
1
1
25
5
6
3
4
1
1
26
12
2
2
11
7
9
8
8
10
1
1
26
11
3
3
12
5
3
4
3
1
1
26
13
13
11
3
3
10
5
3
2
1
1
27
12
13
7
9
8
8
1
1
25
9
10
8
10
10
4
1
1
27
9
10
5
5
4
1
1
27
11
10
8
8
9
9
1
1
27
13
13
13
13
12
11
6
5
7
1
1
26
5
5
9
4
4
3
5
1
1
25
11
1...

output:

? 1 13
? 1 14
? 1 9
? 1 7
? 1 6
! 1 6
? 1 13
? 1 14
? 1 10
? 1 9
? 1 8
? 2 9
? 9 25
! 9 25
? 1 13
? 1 14
? 1 8
? 1 5
? 1 7
? 1 6
? 4 6
? 6 23
! 6 23
? 1 13
? 1 14
? 1 11
? 1 10
? 3 11
! 3 11
? 1 14
? 14 16
? 12 14
? 1 15
? 1 20
? 1 17
? 1 18
? 1 19
? 8 18
? 18 20
! 18 20
? 1 14
? 14 17
? 11 14
? 1 1...

result:

ok ok (1000 test cases)

Test #5:

score: 0
Accepted
time: 13ms
memory: 3620kb

input:

1000
29
10
9
5
3
4
1
1
28
13
2
2
13
6
4
6
2
1
1
30
3
5
3
2
3
1
1
29
4
5
2
3
1
1
28
8
3
7
9
10
8
7
1
1
29
6
5
3
4
1
1
29
9
8
4
6
5
7
1
1
28
11
4
4
12
8
8
9
1
1
30
4
1
1
30
8
3
8
9
10
8
8
1
1
28
11
4
3
10
8
11
11
1
1
29
14
13
8
10
9
9
11
1
1
29
11
12
6
3
4
1
1
29
7
8
10
8
8
1
1
29
14
14
14
13
7
4
2
1
...

output:

? 1 15
? 1 16
? 1 20
? 1 22
? 1 23
? 3 22
! 3 22
? 1 15
? 15 17
? 13 15
? 1 16
? 1 8
? 1 5
? 1 7
? 6 8
? 8 24
! 8 24
? 1 16
? 16 29
? 3 16
? 1 17
? 1 18
? 2 17
! 2 17
? 1 15
? 1 16
? 1 13
? 1 12
? 2 13
! 2 13
? 1 15
? 15 22
? 8 15
? 1 16
? 1 11
? 1 13
? 7 14
? 14 23
! 14 23
? 1 15
? 1 16
? 1 18
? 1 ...

result:

ok ok (1000 test cases)

Test #6:

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

input:

1000
32
13
4
4
14
6
6
5
6
1
1
30
14
2
2
13
7
4
3
4
7
1
1
32
16
16
14
3
3
13
7
6
8
1
1
31
5
6
5
4
1
1
32
7
10
9
6
3
4
1
1
32
8
9
9
7
4
2
3
1
1
31
15
14
8
12
13
12
1
1
31
6
5
3
2
3
3
1
1
32
12
5
5
13
10
11
10
1
1
30
14
2
2
13
7
5
6
6
11
1
1
31
11
12
6
5
5
4
5
1
1
31
10
9
11
11
10
8
1
1
33
7
8
4
2
1
1
...

output:

? 1 17
? 17 21
? 13 17
? 1 18
? 1 10
? 1 7
? 1 9
? 1 8
? 5 9
! 5 9
? 1 16
? 16 18
? 14 16
? 1 17
? 1 23
? 1 26
? 1 28
? 1 27
? 4 26
? 26 28
! 26 28
? 1 17
? 2 18
? 3 19
? 19 22
? 16 19
? 3 20
? 3 26
? 3 29
? 3 27
? 9 26
! 9 26
? 1 16
? 1 17
? 1 14
? 1 15
? 4 15
! 4 15
? 1 17
? 17 27
? 7 17
? 1 18
? ...

result:

ok ok (1000 test cases)

Test #7:

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

input:

1000
34
17
16
2
2
15
8
4
3
4
1
1
33
8
9
8
6
7
1
1
33
11
10
5
5
4
7
1
1
34
11
7
7
12
5
5
4
7
1
1
34
11
7
7
10
5
3
2
3
1
1
35
14
15
7
4
2
1
1
34
8
10
10
9
4
4
3
5
1
1
34
14
4
4
13
7
6
6
5
1
1
34
16
2
2
16
8
4
3
4
1
1
33
9
8
8
6
7
11
1
1
33
16
16
16
16
15
16
9
13
15
1
1
34
16
2
2
15
8
4
2
1
1
33
13
14
...

output:

? 1 18
? 2 19
? 19 21
? 17 19
? 2 20
? 2 27
? 2 31
? 2 33
? 2 32
? 5 31
! 5 31
? 1 17
? 1 18
? 1 13
? 1 15
? 1 14
? 6 15
! 6 15
? 1 17
? 1 18
? 1 23
? 1 25
? 1 24
? 4 24
? 24 31
! 24 31
? 1 18
? 18 25
? 11 18
? 1 19
? 1 12
? 1 10
? 1 11
? 4 11
? 11 32
! 11 32
? 1 18
? 18 25
? 11 18
? 1 19
? 1 24
? 1...

result:

ok ok (1000 test cases)

Test #8:

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

input:

1000
36
18
17
2
1
1
36
3
1
1
36
13
6
6
14
6
5
5
4
1
1
36
5
9
5
6
4
3
1
1
36
18
17
2
2
16
8
5
6
5
1
1
36
12
7
5
11
12
11
10
1
1
35
13
12
11
9
10
13
1
1
36
13
6
5
12
11
13
11
12
1
1
36
14
5
5
13
7
8
6
7
1
1
36
16
3
3
17
10
12
10
9
1
1
36
9
10
9
8
6
6
5
1
1
36
8
9
11
9
4
6
5
7
1
1
36
17
2
2
17
9
13
14
...

output:

? 1 19
? 2 20
? 20 22
? 18 20
! 18 20
? 1 19
? 19 35
! 19 35
? 1 19
? 19 25
? 13 19
? 1 20
? 1 12
? 1 9
? 1 11
? 1 10
? 4 10
! 4 10
? 1 19
? 19 33
? 5 19
? 1 20
? 1 16
? 1 17
? 3 17
! 3 17
? 1 19
? 2 20
? 20 22
? 18 20
? 2 21
? 2 29
? 2 33
? 2 31
? 2 32
? 6 32
! 6 32
? 1 19
? 19 26
? 12 19
? 1 20
? ...

result:

ok ok (1000 test cases)

Test #9:

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

input:

1000
37
17
18
10
13
12
12
2
1
1
36
17
2
2
16
9
12
10
10
16
1
1
38
9
11
5
10
10
8
7
1
1
37
15
14
11
15
13
14
1
1
37
12
13
12
15
13
7
1
1
36
8
9
11
7
4
6
5
7
1
1
37
6
5
3
4
5
1
1
37
18
18
18
18
17
16
8
6
8
9
1
1
37
17
18
10
14
16
17
2
1
1
37
8
7
8
6
7
1
1
37
10
9
5
3
4
5
1
1
37
18
18
18
17
9
5
3
2
1
1...

output:

? 1 19
? 1 20
? 1 11
? 1 15
? 1 13
? 1 14
? 12 14
? 14 27
! 14 27
? 1 19
? 19 21
? 17 19
? 1 20
? 1 28
? 1 24
? 1 26
? 1 27
? 10 26
? 26 28
! 26 28
? 1 20
? 20 31
? 9 20
? 1 21
? 1 15
? 1 17
? 1 18
? 7 18
! 7 18
? 1 19
? 1 20
? 1 27
? 1 23
? 1 21
? 1 22
? 13 21
! 13 21
? 1 19
? 1 20
? 1 13
? 1 16
? ...

result:

ok ok (1000 test cases)

Test #10:

score: 0
Accepted
time: 17ms
memory: 3588kb

input:

1000
39
18
17
11
13
13
14
1
1
38
8
3
12
7
10
8
13
1
1
38
19
19
17
3
3
16
10
14
14
13
1
1
39
12
13
6
3
2
3
1
1
38
15
3
5
14
11
15
15
7
1
1
39
4
3
2
1
1
39
18
19
9
5
3
3
2
1
1
38
18
2
1
1
39
14
13
7
4
2
1
1
39
11
12
10
9
8
9
1
1
39
9
8
4
4
3
1
1
38
19
18
2
1
1
39
15
16
12
14
14
13
5
1
1
38
12
8
8
11
6...

output:

? 1 20
? 1 21
? 1 29
? 1 25
? 1 27
? 1 26
? 13 25
! 13 25
? 1 20
? 20 32
? 8 20
? 1 21
? 1 24
? 1 22
? 7 21
? 21 33
! 21 33
? 1 20
? 2 21
? 3 22
? 22 25
? 19 22
? 3 23
? 3 31
? 3 27
? 3 25
? 3 26
? 15 26
! 15 26
? 1 20
? 1 21
? 1 14
? 1 11
? 1 10
? 1 9
? 2 10
! 2 10
? 1 20
? 20 25
? 15 20
? 1 21
? 1...

result:

ok ok (1000 test cases)

Test #11:

score: 0
Accepted
time: 12ms
memory: 3872kb

input:

1000
40
12
9
9
11
8
9
8
7
1
1
40
18
3
3
17
11
13
13
12
1
1
40
15
6
6
14
7
4
4
3
1
1
40
8
13
13
9
4
2
1
1
40
16
5
5
15
12
16
14
15
9
1
1
40
15
6
6
16
11
11
9
10
6
1
1
41
13
14
7
4
2
1
1
40
7
7
13
6
5
5
4
7
1
1
40
18
3
3
17
11
15
17
16
7
1
1
40
6
11
5
7
5
4
1
1
40
4
7
5
5
2
3
1
1
41
12
11
6
5
5
4
1
1
...

output:

? 1 21
? 21 30
? 12 21
? 1 22
? 1 27
? 1 24
? 1 25
? 1 26
? 7 26
! 7 26
? 1 21
? 21 24
? 18 21
? 1 22
? 1 30
? 1 26
? 1 28
? 1 27
? 12 27
! 12 27
? 1 21
? 21 27
? 15 21
? 1 22
? 1 29
? 1 32
? 1 34
? 1 33
? 3 33
! 3 33
? 1 21
? 21 34
? 8 21
? 1 22
? 1 17
? 1 15
? 1 14
! 1 14
? 1 21
? 21 26
? 16 21
? ...

result:

ok ok (1000 test cases)

Test #12:

score: 0
Accepted
time: 16ms
memory: 3532kb

input:

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

output:

? 1 22
? 22 33
? 11 22
? 1 23
? 1 16
? 1 19
? 1 18
? 1 17
? 6 17
! 6 17
? 1 21
? 1 22
? 1 30
? 1 34
? 1 32
? 1 33
? 5 33
? 33 38
! 33 38
? 1 21
? 1 22
? 1 17
? 1 15
? 1 16
? 3 16
? 16 40
! 16 40
? 1 21
? 1 22
? 1 15
? 1 18
? 1 17
? 1 16
? 7 16
? 16 36
! 16 36
? 1 21
? 1 22
? 1 27
? 1 24
? 1 23
? 10 ...

result:

ok ok (1000 test cases)

Test #13:

score: 0
Accepted
time: 19ms
memory: 3576kb

input:

1000
43
4
5
4
3
1
1
42
18
4
4
19
12
16
17
16
1
1
43
6
7
7
5
6
1
1
43
18
19
11
14
12
11
10
4
1
1
43
21
21
21
20
10
5
4
4
1
1
43
17
18
9
7
7
6
5
1
1
43
18
19
9
5
3
4
1
1
43
21
21
21
20
10
5
3
2
1
1
42
13
9
9
12
8
9
8
7
13
1
1
42
20
2
2
19
11
15
13
12
11
20
1
1
42
5
5
9
6
4
3
5
1
1
43
5
6
3
2
1
1
42
21...

output:

? 1 22
? 1 23
? 1 20
? 1 21
? 3 21
! 3 21
? 1 22
? 22 26
? 18 22
? 1 23
? 1 13
? 1 17
? 1 19
? 1 20
? 16 20
! 16 20
? 1 22
? 1 23
? 1 19
? 1 21
? 1 20
? 5 21
! 5 21
? 1 22
? 1 23
? 1 13
? 1 18
? 1 16
? 1 15
? 1 14
? 10 14
? 14 35
! 14 35
? 1 22
? 1 23
? 2 23
? 2 24
? 2 34
? 2 39
? 2 41
? 2 40
? 5 40...

result:

ok ok (1000 test cases)

Test #14:

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

input:

1000
44
22
22
20
3
3
19
10
5
5
4
1
1
44
11
12
12
10
5
7
6
1
1
43
11
10
13
10
9
15
1
1
43
21
21
21
21
20
19
12
17
17
16
1
1
44
19
4
4
18
9
5
3
2
3
1
1
44
16
7
7
17
8
6
6
5
1
1
44
17
5
6
18
13
17
16
15
6
1
1
44
10
13
5
9
11
9
8
1
1
43
13
14
15
12
12
11
9
1
1
43
4
3
4
5
1
1
44
9
14
5
10
10
8
7
1
1
44
2...

output:

? 1 23
? 2 24
? 3 25
? 25 28
? 22 25
? 3 26
? 3 35
? 3 40
? 3 42
? 3 41
? 6 41
! 6 41
? 1 23
? 23 35
? 11 23
? 1 24
? 1 29
? 1 31
? 1 30
? 5 29
! 5 29
? 1 22
? 1 23
? 1 28
? 1 25
? 1 24
? 9 24
? 24 36
! 24 36
? 1 22
? 1 23
? 2 23
? 2 24
? 3 24
? 3 25
? 3 34
? 3 29
? 3 27
? 3 28
? 18 28
! 18 28
? 1 2...

result:

ok ok (1000 test cases)

Test #15:

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

input:

1000
45
20
21
10
5
3
2
3
3
1
1
45
16
17
8
6
6
5
7
1
1
45
10
11
5
7
6
1
1
45
15
14
7
8
6
7
1
1
45
11
12
6
3
2
3
1
1
45
16
17
10
12
10
9
7
1
1
45
19
18
13
18
16
17
10
1
1
45
5
6
5
4
7
1
1
44
19
4
4
18
9
8
9
8
15
1
1
45
12
11
6
3
2
1
1
44
20
3
3
19
10
7
10
9
17
1
1
45
15
16
8
4
4
3
1
1
44
16
7
7
15
14
...

output:

? 1 23
? 1 24
? 1 13
? 1 8
? 1 6
? 1 5
? 1 4
? 2 5
? 5 45
! 5 45
? 1 23
? 1 24
? 1 15
? 1 11
? 1 13
? 1 12
? 5 12
? 12 42
! 12 42
? 1 23
? 1 24
? 1 18
? 1 16
? 1 17
? 5 18
! 5 18
? 1 23
? 1 24
? 1 31
? 1 34
? 1 32
? 1 33
? 6 32
! 6 32
? 1 23
? 1 24
? 1 18
? 1 15
? 1 14
? 1 13
? 2 14
! 2 14
? 1 23
? ...

result:

ok ok (1000 test cases)

Test #16:

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

input:

1000
46
18
6
6
17
13
13
11
12
1
1
46
9
15
11
8
4
6
5
1
1
46
22
2
2
21
11
7
9
8
7
1
1
46
19
5
5
20
9
7
7
6
1
1
46
5
9
9
6
2
1
1
46
21
3
3
20
12
15
15
14
1
1
46
18
6
6
17
14
13
13
12
1
1
46
16
8
8
15
15
12
14
13
1
1
46
22
2
2
21
12
17
20
21
4
1
1
46
5
9
7
4
2
3
1
1
45
19
18
9
9
7
8
13
1
1
46
14
10
10
...

output:

? 1 24
? 24 30
? 18 24
? 1 25
? 1 33
? 1 29
? 1 31
? 1 32
? 11 31
! 11 31
? 1 24
? 24 39
? 9 24
? 1 25
? 1 29
? 1 31
? 1 30
? 4 29
! 4 29
? 1 24
? 24 26
? 22 24
? 1 25
? 1 35
? 1 40
? 1 37
? 1 38
? 1 39
? 7 39
! 7 39
? 1 24
? 24 29
? 19 24
? 1 25
? 1 14
? 1 10
? 1 12
? 1 11
? 6 11
! 6 11
? 1 24
? 24...

result:

ok ok (1000 test cases)

Test #17:

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

input:

1000
1000000000
499999999
2
2
499999998
249999999
125000001
187500000
156250000
140625000
132812500
128906250
126953126
127929689
128417969
128173829
128051759
127990724
127960206
127944948
127952578
127956392
127954485
127953531
127953054
127952816
127952697
127952637
127952608
127952622
127952616
...

output:

? 1 500000001
? 500000001 500000003
? 499999999 500000001
? 1 500000002
? 1 750000001
? 1 875000000
? 1 812500000
? 1 843750000
? 1 859375000
? 1 867187500
? 1 871093750
? 1 873046875
? 1 872070312
? 1 871582031
? 1 871826171
? 1 871948241
? 1 872009276
? 1 872039794
? 1 872055053
? 1 872047423
? 1 ...

result:

ok ok (1000 test cases)

Test #18:

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

input:

1000
1000000000
499999969
32
32
499999970
250000015
375000007
437499972
406249974
390625006
398437506
402343756
404296850
403320288
402832038
403076179
403198249
403259253
403228767
403244026
403251624
403247841
403249748
403250702
403251148
403250910
403250822
403250882
403250881
403250880
40325087...

output:

? 1 500000001
? 500000001 500000033
? 499999969 500000001
? 1 500000002
? 1 250000016
? 1 375000008
? 1 437500004
? 1 406250006
? 1 390625007
? 1 398437507
? 1 402343757
? 1 404296882
? 1 403320320
? 1 402832039
? 1 403076180
? 1 403198250
? 1 403259285
? 1 403228768
? 1 403244027
? 1 403251656
? 1 ...

result:

ok ok (1000 test cases)

Test #19:

score: 0
Accepted
time: 16ms
memory: 3592kb

input:

1000
1000000000
474148191
25851810
25851810
474148190
237074097
355611143
296342619
266708357
251891226
244482661
240778378
238926237
238000166
237537131
237305613
237189854
237131975
237103035
237088565
237081330
237077713
237075904
237075000
237074548
237074322
237074209
237074152
237074124
237074...

output:

? 1 500000001
? 500000001 525851811
? 474148191 500000001
? 1 500000002
? 1 737074097
? 1 618537049
? 1 677805573
? 1 707439835
? 1 722256966
? 1 729665531
? 1 733369814
? 1 735221955
? 1 736148026
? 1 736611061
? 1 736842579
? 1 736958338
? 1 737016217
? 1 737045157
? 1 737059627
? 1 737066862
? 1 ...

result:

ok ok (1000 test cases)

Test #20:

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

input:

1000
1000000000
230485382
230485311
269514619
230485383
115242763
172864036
144053364
129648028
122445360
118844026
117043359
116143025
115692858
115467775
115355233
115298962
115270827
115256759
115249725
115246208
115244450
115243571
115243131
115242911
115242801
115242746
115242735
115242733
1152...

output:

? 1 500000001
? 500000001 769514620
? 230485382 500000001
? 1 500000002
? 1 384757310
? 1 442378655
? 1 413567983
? 1 399162647
? 1 391959979
? 1 388358645
? 1 386557978
? 1 385657644
? 1 385207477
? 1 384982394
? 1 384869852
? 1 384813581
? 1 384785446
? 1 384771378
? 1 384764344
? 1 384760827
? 1 ...

result:

ok ok (1000 test cases)

Test #21:

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

input:

1000
1000000000
288090905
211909096
211909096
288090904
144045452
72022726
47732739
54017045
45014204
43231318
42763494
42105963
42200817
41919478
41965293
41894958
41884311
41877374
41875520
41872978
41873322
41872223
41872428
41872153
41872086
41872084
41872052
41872067
41872058
41872054
41872052
...

output:

? 1 500000001
? 500000001 711909097
? 288090905 500000001
? 1 500000002
? 1 644045454
? 1 716068180
? 1 752079543
? 1 734073861
? 1 743076702
? 1 747578122
? 1 745327412
? 1 746452767
? 1 745890089
? 1 746171428
? 1 746312097
? 1 746241762
? 1 746206595
? 1 746224178
? 1 746215386
? 1 746219782
? 1 ...

result:

ok ok (1000 test cases)

Test #22:

score: 0
Accepted
time: 52ms
memory: 3876kb

input:

1000
999999999
499999998
499999999
249999999
125000001
187500001
218750000
203125001
210937501
214843751
216796876
217773439
218261720
218505861
218627930
218566896
218597414
218612673
218620301
218616488
218618395
218619348
218618871
218618633
218618515
218618574
218618545
218618559
218618552
21861...

output:

? 1 500000000
? 1 500000001
? 1 250000001
? 1 125000002
? 1 187500002
? 1 218750002
? 1 203125002
? 1 210937502
? 1 214843752
? 1 216796877
? 1 217773440
? 1 218261721
? 1 218505862
? 1 218627932
? 1 218566897
? 1 218597415
? 1 218612674
? 1 218620303
? 1 218616489
? 1 218618396
? 1 218619350
? 1 21...

result:

ok ok (1000 test cases)

Test #23:

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

input:

1000
999999999
499999957
499999956
250000021
374999967
312499973
281250019
296875018
304687517
308593767
310546892
311523454
312011692
311767595
311889622
311828587
311798113
311813372
311821001
311824773
311822909
311823820
311823386
311823625
311823744
311823804
311823834
311823832
311823825
31182...

output:

? 1 500000000
? 1 500000001
? 1 749999979
? 1 624999990
? 1 687499984
? 1 718749981
? 1 703124982
? 1 695312483
? 1 691406233
? 1 689453108
? 1 688476546
? 1 687988265
? 1 688232405
? 1 688110335
? 1 688171370
? 1 688201887
? 1 688186628
? 1 688178999
? 1 688175184
? 1 688177091
? 1 688176137
? 1 68...

result:

ok ok (1000 test cases)

Test #24:

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

input:

1000
999999999
324545945
324545944
162272974
243409458
202841215
182557094
172415033
167344003
164808488
163540730
162906851
162589912
162431442
162352207
162312590
162292781
162282877
162277925
162275449
162274211
162273592
162273282
162273127
162273050
162273011
162272992
162272982
162272977
16227...

output:

? 1 500000000
? 1 500000001
? 1 662272973
? 1 581136487
? 1 621704730
? 1 641988851
? 1 652130912
? 1 657201942
? 1 659737457
? 1 661005215
? 1 661639094
? 1 661956033
? 1 662114503
? 1 662193738
? 1 662233355
? 1 662253164
? 1 662263068
? 1 662268020
? 1 662270496
? 1 662271734
? 1 662272353
? 1 66...

result:

ok ok (1000 test cases)

Test #25:

score: 0
Accepted
time: 29ms
memory: 3640kb

input:

1000
999999999
487015083
487015084
243507608
365261313
304384428
273945985
258726764
251117153
247312348
245409945
244458744
243983143
243745343
243626443
243566993
243537268
243522405
243514974
243511258
243509400
243508471
243508007
243507775
243507659
243507601
243507578
243507587
243507580
24350...

output:

? 1 500000000
? 1 500000001
? 1 256492459
? 1 378246230
? 1 317369345
? 1 286930902
? 1 271711681
? 1 264102070
? 1 260297265
? 1 258394862
? 1 257443661
? 1 256968060
? 1 256730260
? 1 256611360
? 1 256551910
? 1 256522185
? 1 256507322
? 1 256499891
? 1 256496175
? 1 256494317
? 1 256493388
? 1 25...

result:

ok ok (1000 test cases)

Test #26:

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

input:

1000
999999999
265285129
265285128
132642564
66321282
33160641
16580321
8290161
11875165
9802625
8766355
8248220
8031094
8118686
8053919
8021535
8014903
8013439
8010855
8011415
8010403
8010349
8010150
8010223
8010160
8010128
8010134
8010126
8010124
8010124
8010123
1
1
999999999
450448164
450448165
2...

output:

? 1 500000000
? 1 500000001
? 1 632642565
? 1 698963847
? 1 732124488
? 1 748704808
? 1 756994968
? 1 761140048
? 1 759067508
? 1 758031238
? 1 757513103
? 1 757254035
? 1 757383569
? 1 757318802
? 1 757286418
? 1 757270226
? 1 757278322
? 1 757274274
? 1 757276298
? 1 757275286
? 1 757274780
? 1 75...

result:

ok ok (1000 test cases)

Test #27:

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

input:

1000
536870912
261621269
6814188
6814188
261621270
137624821
196215951
170327480
186678809
188040287
186024619
185996371
185002661
185485392
185229903
185102158
185038286
185006350
184990382
184994676
184990684
184988688
184989384
184988885
184988636
184988563
184988574
184988543
184988547
184988539...

output:

? 1 268435457
? 268435457 275249645
? 261621269 268435457
? 1 268435458
? 1 137624822
? 1 203030139
? 1 170327481
? 1 186678810
? 1 194854475
? 1 190766643
? 1 192810559
? 1 191788601
? 1 192299580
? 1 192044091
? 1 191916346
? 1 191852474
? 1 191820538
? 1 191804570
? 1 191796586
? 1 191800578
? 1 ...

result:

ok ok (1000 test cases)

Test #28:

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

input:

1000
536870911
244408485
244408484
122204242
67657827
91653182
76377652
68739887
64921004
65748385
64793664
64443644
64554984
64435644
64383974
64405809
64390891
64383432
64380245
64381567
64380635
64380169
64380012
64380052
64379994
64379983
64379979
64379976
64379975
64379975
64379974
128759947
1
...

output:

? 1 268435456
? 1 268435457
? 1 390639699
? 1 451741820
? 1 421190759
? 1 436466289
? 1 444104054
? 1 447922937
? 1 449832378
? 1 448877657
? 1 448400297
? 1 448638977
? 1 448519637
? 1 448459967
? 1 448489802
? 1 448474884
? 1 448467425
? 1 448463696
? 1 448465560
? 1 448464628
? 1 448464162
? 1 44...

result:

ok ok (1000 test cases)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-02-01 14:04:57 | OpenSource Project