QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783274#7949. K-LotteryNYCU_MyGOAC ✓1022ms12864kbC++206.2kb2024-11-26 06:26:232024-11-26 06:26:23

Judging History

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

  • [2024-11-26 06:26:23]
  • 评测
  • 测评结果:AC
  • 用时:1022ms
  • 内存:12864kb
  • [2024-11-26 06:26:23]
  • 提交

answer

#ifndef MyGO
#define MyGO
#include MyGO __FILE__ MyGO

/*
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
T randint(T x) { return uniform_int_distribution<T>(0, x-1)(rng); }
*/

using ull = unsigned long long;
inline ull splitmix64() {
  static ull x = 0x1337deadbeefcace;
  // change to `static ull x = SEED;` for DRBG
  ull z = (x += 0x9E3779B97F4A7C15);
  z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9;
  z = (z ^ (z >> 27)) * 0x94D049BB133111EB;
  return z ^ (z >> 31);
}

int randint(int x) { return splitmix64() % x; }

constexpr int MAXN = 1e6+5;
constexpr int MAXK = 1e4+5;
constexpr i64 P = 1e6+3;
constexpr i64 MOD = 1e12+39;

i64 PPOW[MAXK];

struct Treap;
using TreapP = Treap*;
struct Treap {
    int sz, data;
    int id; i64 hash;
    TreapP l, r;
    Treap(int k, int i) : sz(1), data(k), id(i), hash(i), l(0), r(0) {}
};
inline int sz(TreapP o) { return o ? o->sz : 0; }
inline i64 H(TreapP o) { return o ? o->hash : 0; }
void pull(TreapP o) {
    auto lsz = sz(o->l), rsz = sz(o->r);
    o->sz = lsz + 1 + rsz;
    o->hash = ((i128)H(o->l) * PPOW[rsz+1] + o->id * PPOW[rsz] + H(o->r)) % MOD;
}
void push(TreapP o) {}
TreapP merge(TreapP a, TreapP b) {
    if (!a or !b) return a ? a : b;
    TreapP r;
    if (randint(sz(a) + sz(b)) < sz(a))
        r = a, push(r), r->r = merge(a->r, b);
    else r = b, push(r), r->l = merge(a, b->l);
    return pull(r), r;
}
void split(TreapP o, TreapP &a, TreapP &b, int k) {
    if (!o) return a = b = 0, void();
    push(o);
    if (o->data <= k)
        a = o, split(o->r, a->r, b, k), pull(a);
    else b = o, split(o->l, a, b->l, k), pull(b);
}
void split2(TreapP o, TreapP &a, TreapP &b, int k) {
    if (sz(o) <= k) return a = o, b = 0, void();
    push(o);
    if (sz(o->l) + 1 <= k)
        a = o, split2(o->r, a->r, b, k - sz(o->l) - 1);
    else b = o, split2(o->l, a, b->l, k);
    pull(o);
}
bool erase(TreapP &o, int k) {
    if (!o) return 0;
    if (o->data == k) {
        TreapP t = o;
        push(o), o = merge(o->l, o->r);
        delete t;
        return 1;
    }
    TreapP &t = k < o->data ? o->l : o->r;
    return erase(t, k) ? pull(o), 1 : 0;
}
void insert(TreapP &o, int k, int v) {
    TreapP a, b;
    split(o, a, b, k);
    o = merge(a, merge(new Treap(k, v), b));
}

void solve() {
    int K, M, N;
    cin >> K >> M >> N;
    vector<vector<int>> tickets(M);
    for (auto &v: tickets) {
        v.resize(K);
        for (auto &x: v) cin >> x;
    }
    vector<int> seq(N);
    for (auto &x: seq) cin >> x;

    vector<i64> Ha(M);
    vector<vector<int>> rev_ticket(M);
    map<i64, vector<int>> mp{};
#pragma GCC ivdep
    for (int i = 0; i < M; i++) {
        auto& v = tickets[i];
        auto& u = rev_ticket[i];
        u.resize(K);
#pragma GCC ivdep
        for (int j = 0; j < K; j++)
            u[v[j]-1] = j+1;
        i64 hash = 0;
#pragma GCC ivdep
        for (auto x: u)
            hash = (hash * P + x) % MOD;
        Ha[i] = hash;
        mp[hash].emplace_back(i);
        assert(hash >= 0 and hash < MOD);
    }
    debug(Ha);

    TreapP root = nullptr;
    for (int i = 0; i < K; i++)
        insert(root, seq[i], i+1);

    i64 idi = 0;
    for (int i = 0; i < K; i++)
        idi = (idi * P + 1) % MOD;
    debug(idi);

    auto check = [=](int x, int y) {
        debug(x, y);
        vector<int> v(seq.begin()+y, seq.begin()+y+K);
        sort(ALL(v));
        debug(v);
        debug(tickets[x]);
#pragma GCC ivdep
        for (int i = 0; i < K; i++)
            if (seq[y+i] != v[tickets[x][i]-1])
                return false;
        return true;
    };

    int ans = -1;

#pragma GCC ivdep
    for (int i = K; i <= N; i++) {
        int p = i - K; // [p, i)
        i64 hh = (H(root) - (i128)idi * p % MOD + MOD) % MOD;
        assert(hh >= 0 and hh < MOD);
        debug(i, hh);

        auto it = mp.find(hh);
        if (it != mp.end()) {
#pragma GCC ivdep
            for (auto x: it->second) {
                if (check(x, p)) {
                    ans = x;
                    break;
                }
            }
            if (ans != -1) break;
        }

        if (i == N) break;
        assert(erase(root, seq[p]));
        insert(root, seq[i], i+1);
    }

    debug(ans);
    // if (ans != -1) debug(tickets[ans]);

    if (ans == -1)
        cout << 0 << '\n';
    else
        for (auto x: tickets[ans])
            cout << x << ' ';
}

int32_t main() {
    fastIO();

    PPOW[0] = 1;
    for (int i = 1; i < MAXK; i++)
        PPOW[i] = PPOW[i-1] * P % MOD;
    
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

#else

#pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("no-math-errno,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
// #pragma GCC target("popcnt,abm,mmx,avx,arch=skylake")

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
// #define int i64
using pii = pair<int, int>;

#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())



ostream& operator<< (ostream& os, const i128 v) {
    return os << (i64)v;
}

template <typename T>
ostream& operator << (ostream &os, const vector<T> &vec) {
    for (int i = 0; i < SZ(vec); ++i) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "\u001b[33m"), \
    fprintf(stderr, "Line %d: (%s) = ", __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) { cerr << _t << "\n"; }
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) { cerr << _t << ", ", _do(_u...); }
#else
#define fastIO() cin.tie(0)->sync_with_stdio(0)
#define debug(...) void()
#endif

template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }

#endif

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 2 10
1 2 3
1 3 2
20 35 10 7 99 53 72 33 88 16

output:

1 3 2 

result:

ok single line: '1 3 2 '

Test #2:

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

input:

4 5 10
1 2 3 4
1 2 4 3
3 4 1 2
4 1 2 3
4 2 3 1
19 31 9 1 89 48 63 30 78 12

output:

4 2 3 1 

result:

ok single line: '4 2 3 1 '

Test #3:

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

input:

3 3 7
1 3 2
2 3 1
2 1 3
11 22 33 44 55 66 77

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 658ms
memory: 12708kb

input:

10000 10 1000000
1 5001 2 5002 3 5003 4 5004 5 5005 6 5006 7 5007 8 5008 9 5009 10 5010 11 5011 12 5012 13 5013 14 5014 15 5015 16 5016 17 5017 18 5018 19 5019 20 5020 21 5021 22 5022 23 5023 24 5024 25 5025 26 5026 27 5027 28 5028 29 5029 30 5030 31 5031 32 5032 33 5033 34 5034 35 5035 36 5036 37 5...

output:

1 5001 2 5002 3 5003 4 5004 5 5005 6 5006 7 5007 8 5008 9 5009 10 5010 11 5011 12 5012 13 5013 14 5014 15 5015 16 5016 17 5017 18 5018 19 5019 20 5020 21 5021 22 5022 23 5023 24 5024 25 5025 26 5026 27 5027 28 5028 29 5029 30 5030 31 5031 32 5032 33 5033 34 5034 35 5035 36 5036 37 5037 38 5038 39 50...

result:

ok single line: '1 5001 2 5002 3 5003 4 5004 5 ...4998 9998 4999 9999 5000 10000 '

Test #5:

score: 0
Accepted
time: 1022ms
memory: 12764kb

input:

10000 10 1000000
7171 4541 8189 3253 6694 2078 7384 1786 7847 5040 953 4126 4806 3532 7875 8531 3543 2706 8565 1509 2092 4125 6110 5251 6314 4574 6726 8900 9328 8639 3990 5234 9012 5023 3289 2825 8038 3593 2249 337 6252 3831 7967 3839 2815 540 3754 1009 8772 2939 2845 5067 6587 2615 375 7252 9940 18...

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 349ms
memory: 12860kb

input:

10000 10 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 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:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 1001ms
memory: 12848kb

input:

10000 10 1000000
3 7 8 1 4 10 2 5 9 6 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:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 1012ms
memory: 12688kb

input:

10000 10 1000000
1 3 7 10 6 4 9 8 2 5 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:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 540ms
memory: 12452kb

input:

100 1000 1000000
34 82 39 96 30 85 83 16 8 31 51 63 76 49 3 7 58 17 42 94 41 9 11 47 89 6 86 19 100 77 37 93 40 15 36 71 23 46 48 55 2 92 64 18 22 21 12 72 1 99 70 81 56 57 53 62 50 35 65 43 73 60 97 24 4 98 20 90 26 68 66 25 74 87 14 67 45 95 33 32 52 29 5 88 54 13 91 10 59 80 28 38 78 61 79 75 69 ...

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 545ms
memory: 12436kb

input:

100 1000 1000000
45 10 54 59 1 86 77 71 61 27 62 26 39 23 21 88 24 85 32 66 53 70 78 90 22 7 72 35 42 76 5 14 16 15 17 51 38 2 46 20 41 56 28 4 57 49 25 97 64 44 8 58 96 29 63 52 89 33 18 94 69 36 43 74 98 40 73 87 65 11 100 60 93 30 13 84 19 80 34 79 31 48 37 12 99 82 92 3 9 67 83 47 50 68 55 91 6 ...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 542ms
memory: 12420kb

input:

100 1000 1000000
31 67 46 23 51 44 16 7 25 73 10 12 64 79 9 77 87 43 84 89 45 54 65 6 62 50 75 78 71 80 32 20 53 35 61 28 96 34 36 14 56 22 42 15 59 72 99 68 33 57 39 40 11 85 3 29 24 1 38 5 8 91 88 37 47 18 86 30 83 4 92 69 49 2 52 90 48 19 27 13 70 21 55 63 74 100 41 94 58 17 97 98 60 76 26 82 81 ...

output:

17 86 68 84 97 39 3 6 94 22 93 80 69 73 60 61 98 59 64 16 77 26 55 58 79 45 40 15 2 35 34 42 70 8 66 41 4 63 28 31 37 72 5 71 83 54 9 25 95 43 36 89 18 96 65 27 62 92 88 87 100 74 91 76 19 48 57 49 14 90 23 38 51 75 20 67 85 24 52 21 30 44 78 50 29 53 32 47 82 81 10 33 7 99 1 11 46 12 56 13 

result:

ok single line: '17 86 68 84 97 39 3 6 94 22 93...81 10 33 7 99 1 11 46 12 56 13 '

Test #12:

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

input:

100 1000 1000000
21 91 95 87 51 53 41 4 83 100 17 80 26 36 40 57 39 28 47 44 32 61 72 13 84 10 14 59 65 96 7 82 93 74 16 22 81 97 98 24 6 86 45 30 54 43 52 1 38 29 5 73 9 15 58 68 71 20 33 42 94 76 46 31 34 19 69 99 56 3 25 49 11 12 18 78 62 35 77 8 85 48 75 92 70 67 60 79 89 88 27 90 63 64 37 55 66...

output:

93 49 8 48 62 87 60 26 76 25 9 79 11 14 53 22 17 94 83 98 31 88 97 95 2 77 13 51 18 86 91 50 23 68 65 96 81 16 71 5 85 54 64 33 3 35 75 15 42 92 1 20 24 100 52 10 84 47 43 80 69 78 30 90 21 66 41 89 27 73 63 36 56 55 38 6 28 46 4 12 74 82 19 39 57 58 67 72 59 34 70 32 37 7 29 44 99 45 40 61 

result:

ok single line: '93 49 8 48 62 87 60 26 76 25 9...4 70 32 37 7 29 44 99 45 40 61 '

Test #13:

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

input:

100 1000 1000000
60 57 14 50 82 3 68 27 5 91 55 19 30 44 84 39 47 98 97 35 83 41 53 4 48 85 34 43 95 54 13 15 12 99 61 9 38 32 29 31 86 65 49 81 40 96 67 77 93 17 18 71 11 73 24 64 80 52 79 92 8 62 21 66 46 20 36 2 74 6 26 69 7 87 42 51 1 45 70 75 28 10 76 100 90 58 33 89 25 56 72 63 22 88 23 94 16 ...

output:

70 9 19 76 46 2 69 24 77 65 75 84 62 18 3 57 63 51 13 52 22 85 96 37 30 71 31 23 21 80 95 61 58 67 99 20 86 10 43 48 35 82 39 54 28 64 14 79 94 44 66 91 73 8 83 27 81 5 49 7 12 55 78 68 92 33 53 59 17 4 45 32 47 97 38 98 40 41 50 15 89 36 87 42 90 26 34 56 93 72 88 6 11 1 29 100 60 74 16 25 

result:

ok single line: '70 9 19 76 46 2 69 24 77 65 75...2 88 6 11 1 29 100 60 74 16 25 '

Test #14:

score: 0
Accepted
time: 55ms
memory: 12464kb

input:

100 1000 1000000
68 33 2 37 1 46 77 61 32 59 11 75 35 63 58 36 99 60 30 28 90 17 50 53 82 65 42 31 19 44 8 98 88 48 38 80 15 93 85 86 24 26 100 95 27 92 13 66 40 81 14 83 5 16 73 51 70 29 69 62 94 41 78 45 71 96 21 64 39 12 91 9 74 25 20 55 43 76 56 22 23 47 84 87 57 10 49 52 4 89 34 97 79 18 6 67 5...

output:

98 41 51 97 30 79 69 83 85 7 15 46 57 6 63 99 94 67 4 27 80 68 16 100 25 1 24 76 82 32 5 56 10 38 81 29 37 60 74 65 31 50 42 88 49 8 78 20 62 18 12 93 34 70 47 13 48 89 72 55 58 21 35 73 39 23 26 96 44 84 61 2 3 95 75 59 87 53 86 91 28 22 36 19 11 9 17 43 77 33 92 40 14 66 45 90 71 52 64 54 

result:

ok single line: '98 41 51 97 30 79 69 83 85 7 1... 92 40 14 66 45 90 71 52 64 54 '

Test #15:

score: 0
Accepted
time: 106ms
memory: 12468kb

input:

100 1000 1000000
93 33 88 40 83 2 54 86 9 82 71 21 5 68 46 39 95 96 84 94 62 61 43 28 99 52 100 34 12 6 66 63 36 18 98 15 17 90 16 11 55 59 53 78 60 80 49 35 4 29 10 32 56 45 7 44 91 23 14 64 73 51 97 20 79 74 92 27 67 69 26 57 41 19 76 87 13 3 72 38 47 65 50 1 8 37 70 85 81 31 58 77 75 24 89 22 25 ...

output:

14 20 15 79 25 38 86 74 58 1 98 83 52 35 92 59 78 63 31 39 8 12 40 17 10 81 95 37 29 67 51 53 48 97 28 72 43 16 77 94 6 7 62 13 47 27 91 89 82 56 84 5 68 85 9 49 73 54 34 55 93 19 69 61 18 23 45 21 57 60 90 44 96 4 100 70 99 11 64 24 76 65 80 71 36 30 26 50 2 46 22 88 32 66 87 33 3 41 75 42 

result:

ok single line: '14 20 15 79 25 38 86 74 58 1 9...6 22 88 32 66 87 33 3 41 75 42 '

Test #16:

score: 0
Accepted
time: 1019ms
memory: 12856kb

input:

10000 10 1000000
8503 3851 9926 1804 9757 5111 3303 9435 6950 7652 9698 4820 4410 997 1022 3781 1995 3752 5332 774 7707 4706 7548 8782 6373 6292 4273 7387 5094 9256 1708 4217 8971 7518 1929 573 7561 9414 152 5560 7293 5085 7073 7349 536 8032 3486 5936 6285 8605 419 4802 1477 564 4619 6219 9714 3056 ...

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 75ms
memory: 12592kb

input:

100 1000 1000000
79 84 77 66 99 93 40 90 20 56 13 12 95 50 63 58 9 74 65 4 14 54 97 25 15 92 37 3 91 52 68 80 39 48 69 2 24 33 44 28 18 22 36 67 7 19 78 87 8 82 64 51 38 83 11 86 43 70 23 42 75 60 21 81 62 6 17 49 26 98 55 73 34 71 29 10 1 94 96 5 46 32 85 30 53 61 31 35 72 76 100 47 27 41 16 89 45 ...

output:

47 59 2 45 15 85 37 71 100 58 86 39 42 36 84 80 3 95 81 29 11 97 23 83 60 14 92 50 52 88 28 31 38 40 10 34 54 26 75 93 72 62 91 12 68 76 27 1 46 78 53 56 22 96 8 13 69 4 6 19 24 32 20 44 61 70 57 51 33 55 77 87 98 48 65 5 43 89 74 7 25 94 18 9 41 49 35 66 16 79 30 82 99 21 67 73 17 64 90 63 

result:

ok single line: '47 59 2 45 15 85 37 71 100 58 ... 30 82 99 21 67 73 17 64 90 63 '

Test #18:

score: 0
Accepted
time: 220ms
memory: 12484kb

input:

100 1000 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 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 99 95 100 ...

output:

0

result:

ok single line: '0'

Test #19:

score: 0
Accepted
time: 225ms
memory: 12464kb

input:

100 1000 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 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 94 98 97 100 99 ...

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 538ms
memory: 12500kb

input:

100 1000 1000000
1 2 3 5 6 4 9 8 10 7 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:

0

result:

ok single line: '0'

Test #21:

score: 0
Accepted
time: 530ms
memory: 12512kb

input:

100 1000 1000000
1 2 3 5 8 6 4 7 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:

0

result:

ok single line: '0'

Test #22:

score: 0
Accepted
time: 1009ms
memory: 12744kb

input:

10000 10 1000000
8198 5263 4423 722 9200 4517 3773 3909 5853 7983 9456 5375 5851 3235 9732 6605 8523 7737 1158 7446 2023 2637 4843 5973 7478 7686 6803 5696 8158 2523 2012 8896 4277 837 2679 1058 7277 4368 4543 3760 3451 8850 74 798 9987 4937 1716 6013 8551 5574 103 5449 7754 9228 1276 3782 5055 7650...

output:

8198 5263 4423 722 9200 4517 3773 3909 5853 7983 9456 5375 5851 3235 9732 6605 8523 7737 1158 7446 2023 2637 4843 5973 7478 7686 6803 5696 8158 2523 2012 8896 4277 837 2679 1058 7277 4368 4543 3760 3451 8850 74 798 9987 4937 1716 6013 8551 5574 103 5449 7754 9228 1276 3782 5055 7650 7266 3507 6852 6...

result:

ok single line: '8198 5263 4423 722 9200 4517 3... 3267 6003 7664 3546 7601 1909 '

Test #23:

score: 0
Accepted
time: 1012ms
memory: 12748kb

input:

10000 10 1000000
6814 3213 874 2526 2829 9116 7887 4398 4066 9912 4620 5143 9472 6782 8366 5348 9670 1639 5113 1691 6115 5395 7256 5193 2880 6931 5576 9075 2906 2473 4269 8487 3156 5347 4581 1915 9464 7009 2564 9220 622 9820 9218 1744 6635 2103 3565 43 6402 2080 6927 1294 3758 9103 6557 2946 4044 68...

output:

519 5743 9913 3782 911 5206 3058 1645 7276 1967 1575 215 7375 2913 9548 4470 7539 7118 866 1399 1031 6037 1212 9539 3552 292 334 9248 9914 3698 6070 1208 5947 8577 1156 5922 5995 4293 8370 1373 5499 5804 8089 3843 2514 5090 6740 9934 9430 159 50 9581 2345 4733 7307 3759 9771 2755 4120 4002 1681 5759...

result:

ok single line: '519 5743 9913 3782 911 5206 30... 2511 8687 6395 9517 1911 5409 '

Test #24:

score: 0
Accepted
time: 62ms
memory: 12840kb

input:

10000 10 1000000
6686 4005 8585 4873 2431 641 7568 4249 6370 9567 2808 5733 3915 6534 2659 4751 6226 5882 6840 2032 1187 3270 3871 5952 6901 9290 6687 3271 2195 1614 2118 9991 7922 6051 8319 1242 8007 6116 5485 9846 1010 6722 9436 6242 646 9958 6553 129 1131 2824 3162 9863 375 555 3684 5728 222 352 ...

output:

1810 6588 8889 6692 2290 6849 7214 9958 7894 9031 9308 6490 3039 9051 6954 4780 2456 3905 8351 4096 9434 1546 3424 5017 4504 2779 3274 6075 5794 3505 7758 6398 2276 2640 7852 6589 6793 3221 9709 4804 1740 7132 3386 737 2587 3056 5993 8967 283 3521 5892 8233 9963 7381 4414 6436 7215 179 4103 8765 878...

result:

ok single line: '1810 6588 8889 6692 2290 6849 ...5 8933 8568 369 2086 8456 1807 '

Test #25:

score: 0
Accepted
time: 64ms
memory: 12800kb

input:

10000 10 1000000
789 6150 5652 1241 1715 4505 3801 5663 238 9096 8451 7244 5284 7391 4374 127 2293 7598 8098 5054 1724 4235 9913 1135 1003 6124 8760 9679 4770 6465 3756 9157 5441 202 593 4782 2360 4974 5488 1566 7464 4577 2481 5601 3013 5385 1685 7537 4566 9672 8565 3203 9456 4690 585 4209 8820 9266...

output:

9185 8306 6829 1442 9007 9092 5328 810 8006 8133 2802 9193 5812 1969 982 7881 8056 2178 152 1430 7230 8898 2944 3685 3183 2329 6379 8454 2698 3077 786 6027 1304 8389 9234 4240 7041 9884 292 2030 3676 2414 7577 3923 365 2430 646 6203 4959 4586 3313 5102 8358 2239 2519 6192 5963 1668 9178 9842 9183 39...

result:

ok single line: '9185 8306 6829 1442 9007 9092 ...3 4438 9006 795 2999 5428 1580 '

Test #26:

score: 0
Accepted
time: 480ms
memory: 12852kb

input:

10000 10 1000000
566 1671 9285 5769 6096 3728 5208 1059 7450 5253 8182 6822 4697 806 7296 407 2806 9850 6109 8711 9360 5399 1551 7241 4409 7927 8255 976 3022 2105 6050 1016 6656 2235 4003 7769 5066 7290 1065 3901 221 6389 7588 2850 5504 6950 3539 649 2031 6330 9034 2755 8442 3245 331 7574 3 1827 208...

output:

1731 4333 2981 6941 9424 9409 2500 4401 197 2920 6163 9232 9538 4370 5815 6057 4287 5901 2371 5676 5057 2521 5006 7991 1235 4204 6553 8741 8794 7500 9984 9490 4603 5573 5251 8724 3759 3661 6883 8495 3986 3979 6344 9604 6982 2471 9244 2059 7575 591 4801 6313 4180 1670 3092 9907 2307 8826 1900 9387 71...

result:

ok single line: '1731 4333 2981 6941 9424 9409 ...102 408 6526 2296 3237 3518 77 '

Test #27:

score: 0
Accepted
time: 231ms
memory: 12864kb

input:

10000 10 1000000
416 3880 4723 3574 1056 3810 6914 4100 103 1460 5550 2737 9212 4634 7676 6449 8863 7068 5141 1631 6290 3762 3129 5610 8709 5790 5819 4035 9787 5405 8645 1113 9438 2726 3795 7189 976 5119 1295 7431 6377 8436 6315 7349 2764 2866 3890 2255 9511 905 9211 7931 4641 7626 2205 4290 6777 78...

output:

4181 9293 5899 1778 9918 8899 2820 2306 3004 4822 3584 2632 6867 6858 7196 968 4910 5391 586 2382 8031 6669 2986 7208 3902 3278 6588 9340 9724 2563 1674 6338 3128 7345 4605 2757 2510 2185 168 6823 8760 1370 5254 7933 5647 5462 1103 2411 4174 7676 1802 2169 1993 2244 5096 2222 9980 6231 9823 8102 392...

result:

ok single line: '4181 9293 5899 1778 9918 8899 ... 4043 1465 3359 6922 4918 7286 '

Test #28:

score: 0
Accepted
time: 353ms
memory: 12780kb

input:

10000 10 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 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:

0

result:

ok single line: '0'