QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310976#6400. Game: Celestememset0AC ✓920ms538292kbC++205.1kb2024-01-21 20:18:182024-01-21 20:18:18

Judging History

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

  • [2024-01-21 20:18:18]
  • 评测
  • 测评结果:AC
  • 用时:920ms
  • 内存:538292kb
  • [2024-01-21 20:18:18]
  • 提交

answer

#include <bits/stdc++.h>
#ifndef popteam
#define endl '\n'
#endif
#define all(x) begin(x), end(x)
using namespace std;
using ull = unsigned long long;
const int N = 1e6 + 9;
int T, n, xl, xr, nod, x[N], a[N], cnt[N];
vector<int> hsh[N];
vector<int> tmp;
mt19937_64 rng(20040129);
// struct sequence {
//     vector<int> v;
//     bool empty() { return v.empty(); }
//     void reset() { v.clear(); }
//     bool operator>(const sequence &rhs) const {
//         for (size_t i = 0; i < v.size() && i < rhs.v.size(); i++)
//             if (v[i] != rhs.v[i]) {
//                 return v[i] > rhs.v[i];
//             }
//         return v.size() > rhs.v.size();
//     }
//     sequence insert(int x) {
//         sequence it = *this;
//         it.v.push_back(x);
//         sort(all(it.v), [&](int x, int y) { return x > y; });
//         return it;
//     }
// } f[N];
struct node {
    int lc, rc, cnt;
    ull hsh;
} e[N * 22];
void maintain(int u) {
    e[u].cnt = 0;
    e[u].hsh = 0;
    if (e[u].lc) {
        e[u].cnt += e[e[u].lc].cnt;
        e[u].hsh ^= e[e[u].lc].hsh;
    }
    if (e[u].rc) {
        e[u].cnt += e[e[u].rc].cnt;
        e[u].hsh ^= e[e[u].rc].hsh;
    }
}
void insert(int &u, int v, int k, int l, int r) {
    u = ++nod;
    // fprintf(stderr, "insert %d %d %d %d %d\n", u, v, k, l, r);
    if (l == r) {
        e[u].cnt = (v ? e[v].cnt : 0) + 1;
        e[u].hsh = hsh[l][e[u].cnt];
        return;
    }
    int mid = (l + r) >> 1;
    if (k <= mid) {
        e[u].rc = e[v].rc;
        insert(e[u].lc, e[v].lc, k, l, mid);
    } else {
        e[u].lc = e[v].lc;
        insert(e[u].rc, e[v].rc, k, mid + 1, r);
    }
    maintain(u);
    // fprintf(stderr, "end insert %d[%d %llu]\n", u, e[u].cnt, e[u].hsh);
}
bool cmp(int u, int v, int l, int r) {
    if (!u || !v) {
        return u < v;
    }
    if (l == r) {
        return e[u].cnt < e[v].cnt;
    }
    int mid = (l + r) >> 1;
    if (e[e[u].rc].hsh != e[e[v].rc].hsh) {
        return cmp(e[u].rc, e[v].rc, mid + 1, r);
    } else {
        return cmp(e[u].lc, e[v].lc, l, mid);
    }
}
void dfs(int u, vector<int> &ans, int l, int r) {
    // fprintf(stderr, "dfs %d[%d %llu] %d %d %d\n", u, e[u].cnt, e[u].hsh, (int)ans.size(), l, r);
    if (!u || !e[u].cnt) return;
    if (l == r) {
        for (int _ = e[u].cnt; _--;) {
            ans.push_back(l);
        }
        return;
    }
    int mid = (l + r) >> 1;
    dfs(e[u].rc, ans, mid + 1, r);
    dfs(e[u].lc, ans, l, mid);
}
struct sequence {
    int rt;
    bool empty() { return rt == 0; }
    void reset() { rt = 0; }
    bool operator>(const sequence &rhs) const { return cmp(rhs.rt, rt, 1, tmp.size()); }
    sequence insert(int x) {
        // fprintf(stderr, "insert x=%d\n", x);
        sequence res = *this;
        ::insert(res.rt, rt, x, 1, tmp.size());
        return res;
    }
} f[N];
deque<pair<int, sequence>> q;
int main() {
#ifdef popteam
    freopen("G.in", "r", stdin);
    // freopen("G.out", "w", stdout);
#endif
    cin.tie(0)->sync_with_stdio(0);
    cin >> T;
    while (T--) {
        nod = 0;
        cin >> n >> xl >> xr;
        for (int i = 1; i <= n; i++)
            cin >> x[i];
        tmp.clear();
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            tmp.push_back(a[i]);
        }
        sort(all(tmp));
        tmp.erase(unique(all(tmp)), tmp.end());
        fill_n(cnt + 1, tmp.size(), 0);
        for (int i = 1; i <= n; i++) {
            a[i] = lower_bound(all(tmp), a[i]) - tmp.begin() + 1;
            cnt[a[i]]++;
        }
        // for (int i = 1; i <= n; i++)
        //     cerr << a[i] << " \n"[i == n];
        for (int i = 1; i <= tmp.size(); i++) {
            while (hsh[i].size() <= cnt[i]) {
                hsh[i].push_back(rng());
            }
        }
        q.clear();
        int j = 1;
        for (int i = 1; i <= n; i++) {
            while (j < i && x[j] + xl <= x[i]) {
                if (!f[j].empty()) {
                    while (q.size() && f[j] > q.back().second) {
                        q.pop_back();
                    }
                    q.push_back(make_pair(j, f[j]));
                }
                j++;
            }
            while (q.size() && x[q.front().first] + xr < x[i]) {
                q.pop_front();
            }
            // fprintf(stderr, "i=%d :: ", i);
            // for (auto x : q)
            //     cerr << x.first << " ";
            // cerr << endl;
            if (q.size()) {
                f[i] = q.front().second.insert(a[i]);
            } else {
                f[i].reset();
                if (i == 1) {
                    f[i] = f[i].insert(a[1]);
                }
            }
        }
        if (f[n].empty()) {
            cout << -1 << endl;
        } else {
            vector<int> ans;
            dfs(f[n].rt, ans, 1, tmp.size());
            cout << ans.size() << endl;
            for (int i = 0; i < ans.size(); i++) {
                cout << tmp[ans[i] - 1] << " \n"[i + 1 == ans.size()];
            }
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 11800kb

input:

2
5 2 3
1 2 3 4 5
5 2 3 1 4
3 1 2
1 4 7
3 3 3

output:

3
5 4 3
-1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 178ms
memory: 11940kb

input:

10000
57 8 11
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 1...

output:

7
20 20 19 14 12 11 3
-1
6
6 5 3 2 1 1
-1
185
20 20 20 20 20 20 20 20 19 19 19 19 19 19 19 19 19 19 19 19 18 18 18 18 18 17 17 17 17 17 17 17 17 16 16 16 16 16 16 16 16 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 14 14 14 14 14 14 14 13 13 13 13 13 13 13 13 13 12 12 12 12 12 12 12 12...

result:

ok 16378 lines

Test #3:

score: 0
Accepted
time: 160ms
memory: 12128kb

input:

10000
86 230405 991217
3291 11742 17120 30018 47955 52215 96227 98031 100118 106944 117304 121905 124796 135037 164100 164654 169459 177527 206513 212554 228740 229590 261521 295062 300116 312030 326533 329513 349983 353580 355242 356731 363347 368753 389545 396163 399755 409927 426532 427781 441386...

output:

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

result:

ok 14975 lines

Test #4:

score: 0
Accepted
time: 146ms
memory: 12116kb

input:

10000
101 17 17
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

-1
15
10 10 10 10 10 10 9 9 9 9 7 7 6 6 3
-1
44
10 10 10 10 10 10 10 10 10 10 10 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 8 8 8 7 6 6 6 6 6 6 6 5 4 3 3 3 3
11
10 10 10 10 10 9 8 7 6 6 2
6
10 10 10 10 8 3
18
10 10 10 10 10 10 8 8 8 8 7 7 7 6 5 3 2 2
-1
-1
1
1
-1
-1
-1
20
10 10 10 10 10 10 10 10 10 9 8 8 8 8 7...

result:

ok 16344 lines

Test #5:

score: 0
Accepted
time: 99ms
memory: 11884kb

input:

10000
18 16 16
1 2 3 4 5 6 7 8 10 11 12 13 14 16 17 18 19 20
2 2 2 1 2 1 1 2 2 2 2 1 2 2 1 2 1 1
403 3 7
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 ...

output:

-1
126
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
-1
-1
-1
1
1
-1
-1
10
2 2 2 2 2 2 1 1 1 1...

result:

ok 16420 lines

Test #6:

score: 0
Accepted
time: 111ms
memory: 11764kb

input:

10000
251 1 1
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

251
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok 16925 lines

Test #7:

score: 0
Accepted
time: 182ms
memory: 20344kb

input:

100
23882 222 481
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

output:

102
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 19...

result:

ok 167 lines

Test #8:

score: 0
Accepted
time: 154ms
memory: 22664kb

input:

100
3789 29850 70419
774 1032 1649 1723 2194 3021 3114 3308 3344 3360 3688 3781 3967 4245 4878 4966 5099 5597 5617 5638 5645 5784 5871 6136 6158 6358 6483 6600 6766 6775 6800 6895 7119 7439 7485 7696 7734 8432 8493 8581 8627 9203 9576 9885 10062 10290 10454 10466 10537 10717 10861 11048 11484 11497 ...

output:

30
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 19 18 3
-1
-1
-1
4
20 20 18 10
-1
6
20 20 20 20 15 9
-1
-1
5
20 20 20 18 4
4
20 20 13 7
-1
4
20 20 19 18
-1
-1
-1
-1
2
16 8
-1
3
20 20 6
8
20 20 20 20 20 20 15 12
-1
-1
-1
17
20 20 20 20 20 20 20 20 20 20 20 20 20 20...

result:

ok 139 lines

Test #9:

score: 0
Accepted
time: 156ms
memory: 18060kb

input:

100
181 1947 1967
17 23 47 53 55 68 84 92 110 147 153 164 191 198 207 209 215 221 255 269 275 302 305 322 324 363 370 373 385 405 407 429 451 458 466 472 478 500 508 544 557 561 564 565 569 587 600 610 617 630 645 659 665 670 674 715 726 744 747 764 769 770 774 782 786 787 794 795 824 852 860 873 87...

output:

-1
-1
-1
12
10 10 10 10 10 10 10 10 10 10 9 4
12
10 10 10 10 10 10 10 10 10 10 5 5
13
10 10 10 10 10 10 10 10 10 10 10 5 4
-1
22
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 5 2
215
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1...

result:

ok 166 lines

Test #10:

score: 0
Accepted
time: 121ms
memory: 15564kb

input:

100
5589 851 904
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

-1
267
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

result:

ok 184 lines

Test #11:

score: 0
Accepted
time: 94ms
memory: 17304kb

input:

100
6944 1905 1926
2 3 4 6 7 8 9 10 11 13 15 16 17 18 20 22 23 24 25 29 31 32 33 34 35 39 40 42 43 44 45 46 47 49 51 54 55 57 58 60 61 62 63 64 67 68 69 71 72 74 75 76 78 79 80 81 82 83 84 85 86 90 91 92 94 95 96 98 100 104 105 106 107 108 109 111 112 117 118 119 120 123 125 126 127 128 131 133 134 ...

output:

-1
-1
296
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

result:

ok 118 lines

Test #12:

score: 0
Accepted
time: 131ms
memory: 30308kb

input:

10
93999 762 838
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

124
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1
2332
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

result:

ok 20 lines

Test #13:

score: 0
Accepted
time: 120ms
memory: 46176kb

input:

10
10628 1687 1731
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97...

output:

-1
-1
76
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
-1
-1
219
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

result:

ok 13 lines

Test #14:

score: 0
Accepted
time: 265ms
memory: 30932kb

input:

3
187063 95635158 95636093
11 507 618 934 1132 2191 3177 3365 3571 3605 4833 4988 5100 6157 6542 7005 7008 7258 7353 7366 7507 9327 10129 10131 10240 11168 11397 12964 13519 14429 14748 15782 16126 16244 16491 17464 17693 18411 19312 19807 19967 20183 21049 21170 21526 21813 22278 22946 23297 23600 ...

output:

-1
-1
-1

result:

ok 3 lines

Test #15:

score: 0
Accepted
time: 122ms
memory: 46364kb

input:

3
109970 343649 521308
4 6 25 27 32 45 53 56 76 81 100 111 115 133 143 145 163 169 173 174 194 199 243 261 299 300 303 311 332 335 341 357 367 368 374 387 392 412 415 422 435 437 442 443 444 454 458 462 466 478 482 486 490 497 499 505 512 521 528 544 549 558 560 574 587 597 620 622 625 643 651 652 6...

output:

3
2 2 1
-1
8
2 2 2 2 2 2 1 1

result:

ok 5 lines

Test #16:

score: 0
Accepted
time: 98ms
memory: 38452kb

input:

3
541782 286 289
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

1895
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

result:

ok 5 lines

Test #17:

score: 0
Accepted
time: 699ms
memory: 273584kb

input:

2
590573 45 48
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

12722
100000 100000 100000 100000 100000 100000 100000 99999 99999 99999 99999 99999 99999 99998 99998 99998 99998 99998 99998 99998 99998 99998 99998 99998 99998 99998 99998 99997 99997 99997 99997 99997 99996 99996 99996 99995 99995 99994 99994 99994 99994 99994 99994 99994 99993 99993 99993 99993...

result:

ok 4 lines

Test #18:

score: 0
Accepted
time: 285ms
memory: 144344kb

input:

2
658290 51 71
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

11109
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 10...

result:

ok 4 lines

Test #19:

score: 0
Accepted
time: 837ms
memory: 534812kb

input:

1
1000000 324190 960223
187 199 240 453 559 628 670 753 755 1329 1330 1681 1904 2042 2061 2169 2183 2233 2258 2535 2555 2711 2718 2819 2951 3211 3294 3309 3342 3456 3485 3491 3782 3834 3854 3968 4205 4236 4312 4314 4340 4371 4596 4603 4734 4792 5133 5249 5273 5469 5895 5915 5977 6006 6029 6062 6089 ...

output:

231
1000000 1000000 999999 999999 999999 999999 999999 999997 999997 999992 999992 999992 999992 999991 999989 999987 999987 999985 999985 999983 999982 999981 999981 999978 999976 999975 999975 999973 999970 999969 999969 999969 999968 999968 999965 999963 999962 999960 999960 999959 999957 999952 ...

result:

ok 2 lines

Test #20:

score: 0
Accepted
time: 104ms
memory: 30428kb

input:

1
1000000 87283396 87283923
47 91 155 190 566 594 1076 1200 1393 1419 1433 1460 1928 1971 1980 1984 2044 2240 2269 2289 2524 2630 2644 2655 2718 2724 2937 3196 3321 3352 3354 3387 3430 3480 3553 3589 3837 3853 3868 4307 4374 4404 4486 4512 4521 4715 4776 4810 4962 5060 5067 5081 5153 5313 5330 5409 ...

output:

-1

result:

ok single line: '-1'

Test #21:

score: 0
Accepted
time: 280ms
memory: 32984kb

input:

1
1000000 72210945 72247561
83 183 329 485 537 555 722 867 874 1021 1092 1350 1362 1410 1544 1740 1812 1823 1846 1870 2188 2194 2304 2335 2383 2539 2709 2745 2807 3094 3151 3231 3238 3253 3390 3573 3579 3596 3672 3700 3721 3750 3811 4125 4178 4191 4202 4330 4339 4601 4631 4641 4684 4834 4997 5037 52...

output:

-1

result:

ok single line: '-1'

Test #22:

score: 0
Accepted
time: 920ms
memory: 538292kb

input:

1
1000000 7 9
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

127372
1000000 999999 999999 999997 999997 999996 999996 999995 999992 999991 999989 999989 999988 999988 999987 999985 999985 999985 999984 999982 999981 999981 999977 999977 999974 999974 999974 999974 999974 999972 999972 999972 999972 999971 999971 999971 999970 999969 999967 999966 999963 99996...

result:

ok 2 lines

Test #23:

score: 0
Accepted
time: 537ms
memory: 371684kb

input:

1
1000000 1 4
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

1000000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 1000...

result:

ok 2 lines

Test #24:

score: 0
Accepted
time: 245ms
memory: 216044kb

input:

1
1000000 1 1
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

1000000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

result:

ok 2 lines

Test #25:

score: 0
Accepted
time: 140ms
memory: 13796kb

input:

100000
13 9192 9313
242 601 1041 2455 3952 5255 6287 6432 6788 7101 7444 8442 9180
13 13 13 13 13 13 13 13 13 13 13 13 13
13 9740 9943
159 1009 2672 2928 3588 4323 5302 6037 6059 6383 6864 8722 9587
13 13 13 13 13 13 13 13 13 13 13 13 13
1 8092 9788
6964
1
6 573 6265
2326 5315 6299 6374 6600 7104
6 ...

output:

-1
-1
1
1
4
6 6 6 6
-1
-1
2
14 14
2
4 4
1
1
2
13 13
2
5 5
-1
7
8 8 8 7 6 6 5
2
43 43
-1
-1
-1
2
5 5
-1
-1
-1
2
2 2
1
1
2
9 9
3
12 12 11
6
44 44 44 44 44 41
-1
1
1
-1
-1
-1
-1
-1
2
7 7
-1
-1
4
15 15 15 15
7
9 9 9 8 8 8 6
1
1
2
4 4
-1
4
12 12 12 9
4
5 5 5 5
4
9 9 9 9
-1
-1
-1
3
22 22 22
-1
3
8 8 7
1
1...

result:

ok 149287 lines

Test #26:

score: 0
Accepted
time: 155ms
memory: 15112kb

input:

1000
358 1293 2838
3 54 136 140 151 202 218 262 279 306 345 349 355 361 368 375 414 428 446 488 491 535 543 556 626 655 694 701 744 753 797 820 857 874 952 968 990 1073 1079 1099 1116 1117 1160 1161 1205 1211 1249 1266 1278 1293 1315 1351 1393 1470 1473 1478 1489 1504 1540 1543 1554 1560 1645 1668 1...

output:

7
358 358 357 314 313 308 304
4
132 132 130 107
6
39 39 35 31 25 14
5
388 388 387 286 196
3
115 115 112
-1
-1
3
1045 1045 1044
-1
4
244 244 243 175
-1
-1
-1
5
564 564 563 444 323
4
84 84 82 78
18
18 18 17 17 16 16 16 16 15 15 15 15 15 14 14 14 14 13
-1
2
332 332
-1
-1
6
1441 1441 1439 1172 936 718
3...

result:

ok 1498 lines

Test #27:

score: 0
Accepted
time: 196ms
memory: 65408kb

input:

10
175986 5404 8551
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...

output:

33
175986 175986 175986 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841 172841
154
35190 35190 35190 34962 34734 34506 34277 34050 33820 33594 33...

result:

ok 17 lines

Test #28:

score: 0
Accepted
time: 184ms
memory: 137200kb

input:

3
204792 277 290
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

737
204792 204792 204791 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 204780 20...

result:

ok 6 lines

Test #29:

score: 0
Accepted
time: 147ms
memory: 104256kb

input:

2
809079 10 17
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

80908
809079 809079 809078 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 809072 ...

result:

ok 4 lines

Test #30:

score: 0
Accepted
time: 113ms
memory: 39656kb

input:

1
1000000 2 2
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

-1

result:

ok single line: '-1'

Test #31:

score: 0
Accepted
time: 134ms
memory: 12048kb

input:

100000
14 3059 9856
246 301 1036 1150 1457 4759 5272 6059 6562 6943 7213 7938 7951 8263
8 8 7 7 6 13 14 14 14 14 14 14 14 14
18 6393 9188
681 1859 3208 3227 3450 3522 3738 4194 4942 5364 5467 7190 7505 7641 7702 8269 8811 8960
13 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18
13 9534 9664
1114 1...

output:

3
14 13 8
2
18 13
-1
-1
-1
2
17 17
-1
-1
2
5 5
3
7 7 6
1
1
-1
2
19 14
4
9 9 8 6
-1
-1
-1
2
5 5
-1
-1
2
26 25
-1
-1
5
15 15 9 5 4
3
3 3 3
13
33 33 32 32 31 30 28 28 27 27 26 25 23
-1
4
10 10 7 6
4
9 9 9 8
-1
2
5 5
3
12 12 7
1
1
1
1
4
7 7 7 3
2
21 18
2
2 2
-1
1
1
4
11 11 9 8
-1
-1
3
15 15 13
-1
-1
-1
...

result:

ok 149206 lines

Test #32:

score: 0
Accepted
time: 152ms
memory: 14944kb

input:

1000
44 7397 8338
216 407 849 862 1353 1368 1386 1570 1606 1754 2039 2049 2098 2548 2787 3205 3971 3989 4088 4464 4663 4879 5524 5691 5705 5899 5908 6545 6795 6921 6923 6963 6982 7309 7359 7617 8344 8411 8585 8993 9528 9547 9570 9931
42 42 41 41 41 41 41 41 41 41 41 41 41 44 44 44 44 44 44 44 44 44 ...

output:

-1
6
1232 1232 1010 786 664 657
3
1284 1206 1090
15
824 823 758 695 633 573 522 462 442 436 427 422 414 412 403
3
365 342 277
5
395 395 289 270 257
5
429 429 327 238 177
5
1013 1013 758 488 403
-1
2
19 19
8
849 848 823 816 814 805 801 801
4
1156 1156 883 469
-1
-1
-1
223
1813 1813 1806 1798 1787 178...

result:

ok 1524 lines

Test #33:

score: 0
Accepted
time: 215ms
memory: 99532kb

input:

10
94483 2348 5947
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97...

output:

41
94483 94483 92136 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90886 90884
102
331929 331929 331382 331382 331382 331382 33138...

result:

ok 19 lines

Test #34:

score: 0
Accepted
time: 209ms
memory: 129584kb

input:

3
728742 717 741
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

1016
728742 728742 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 728719 7...

result:

ok 6 lines

Test #35:

score: 0
Accepted
time: 139ms
memory: 73828kb

input:

2
700712 48 50
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

14599
700712 700712 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 700710 ...

result:

ok 4 lines

Test #36:

score: 0
Accepted
time: 123ms
memory: 39476kb

input:

1
1000000 2 2
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

-1

result:

ok single line: '-1'