QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725488#7949. K-LotterylmqzzzTL 1938ms148252kbC++2011.9kb2024-11-08 18:15:232024-11-08 18:15:23

Judging History

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

  • [2024-11-08 18:15:23]
  • 评测
  • 测评结果:TL
  • 用时:1938ms
  • 内存:148252kb
  • [2024-11-08 18:15:23]
  • 提交

answer

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

namespace std {

template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
    static_assert(D >= 1, "Dimension must be positive");
    template <typename... Args>
    Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};

template <typename T>
struct Vec<1, T> : public vector<T> {
    Vec(int n = 0, T val = T()) : std::vector<T>(n, val) {}
};

/* Example
    Vec<4, int64_t> f(n, k, 2, 2); // = f[n][k][2][2];
    Vec<2, int> adj(n); // graph
*/

template <class Fun>
class y_combinator_result {
    Fun fun_;

   public:
    template <class T>
    explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {}

    template <class... Args>
    decltype(auto) operator()(Args&&... args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

/* Example
    auto fun = y_combinator([&](auto self, int x) -> void {
        self(x + 1);
    });
*/

}  // namespace std

template <typename T>
T inverse(T a, T m) {
    T u = 0, v = 1;
    while (a != 0) {
        T t = m / a;
        m -= t * a;
        swap(a, m);
        u -= t * v;
        swap(u, v);
    }
    assert(m == 1);
    return u;
}

template <typename T>
class Modular {
   public:
    using Type = typename decay<decltype(T::value)>::type;

    constexpr Modular() : value() {}
    template <typename U>
    Modular(const U& x) {
        value = normalize(x);
    }

    template <typename U>
    static Type normalize(const U& x) {
        Type v;
        if (-mod() <= x && x < mod())
            v = static_cast<Type>(x);
        else
            v = static_cast<Type>(x % mod());
        if (v < 0) v += mod();
        return v;
    }

    const Type& operator()() const { return value; }
    template <typename U>
    explicit operator U() const { return static_cast<U>(value); }
    constexpr static Type mod() { return T::value; }

    Modular& operator+=(const Modular& other) {
        if ((value += other.value) >= mod()) value -= mod();
        return *this;
    }
    Modular& operator-=(const Modular& other) {
        if ((value -= other.value) < 0) value += mod();
        return *this;
    }
    template <typename U>
    Modular& operator+=(const U& other) { return *this += Modular(other); }
    template <typename U>
    Modular& operator-=(const U& other) { return *this -= Modular(other); }
    Modular& operator++() { return *this += 1; }
    Modular& operator--() { return *this -= 1; }
    Modular operator++(int) {
        Modular result(*this);
        *this += 1;
        return result;
    }
    Modular operator--(int) {
        Modular result(*this);
        *this -= 1;
        return result;
    }
    Modular operator-() const { return Modular(-value); }

    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
        return *this;
    }
    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
        long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
    }
    template <typename U = T>
    typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
        value = normalize(value * rhs.value);
        return *this;
    }

    Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

    friend const Type& abs(const Modular& x) { return x.value; }

    template <typename U>
    friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

    template <typename U>
    friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

    template <typename V, typename U>
    friend V& operator>>(V& stream, Modular<U>& number);

   private:
    Type value;
};

template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    U p = b;
    while (p > 0) {
        if (p & 1) res *= x;
        x *= x;
        p >>= 1;
    }
    return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) {
    return number() == 0;
}

template <typename T>
string to_string(const Modular<T>& number) {
    return to_string(number());
}

// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
    return stream << number();
}

// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
    typename common_type<typename Modular<T>::Type, long long>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
}

/*
using ModType = int;

struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using uint64_t = Modular<VarMod>;
*/

constexpr int md = 1e9 + 2277;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);

Mint C(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    while ((int)fact.size() < n + 1) {
        fact.push_back(fact.back() * (int)fact.size());
        inv_fact.push_back(1 / fact.back());
    }
    return fact[n] * inv_fact[k] * inv_fact[n - k];
}

const uint64_t base = 2793853;

class segtree_t {
   public:
    segtree_t *left, *right;
    int l, r, m;
    uint64_t val, lazy;

    segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val(0), lazy(1) {
        if (l == r) return;
        left = new segtree_t(l, m);
        right = new segtree_t(m + 1, r);
    }

    void Update(int p, uint64_t x) {
        if (l == r) {
            val = x;
            return;
        }
        Down();
        if (p <= m) {
            left->Update(p, x);
        } else {
            right->Update(p, x);
        }
        Up();
    }

    void Update(int s, int t, uint64_t x) {
        if (r < s || l > t) return;
        if (s <= l && r <= t) {
            val *= x;
            lazy *= x;
            return;
        }
        Down();
        left->Update(s, t, x);
        right->Update(s, t, x);
        Up();
    }

    void Up() {
        val = left->val + right->val;
    }

    void Down() {
        if (lazy == 1) return;
        left->lazy *= lazy;
        right->lazy *= lazy;
        right->val *= lazy;
        left->val *= lazy;
        lazy = 1;
    }
};

template <class T>
class fenwick_t {
   public:
    vector<T> bit;
    int n;

    fenwick_t(int n = 0) : n(n) {
        bit.resize(n + 5, 0);
    }

    void Update(int pos, T val) {
        for (pos++; pos < bit.size(); pos += pos & -pos) {
            bit[pos] += val;
        }
    }

    T Get(int pos) {
        T res = T(0);
        for (pos++; pos > 0; pos -= pos & -pos) {
            res += bit[pos];
        }
        return res;
    }

    T Get(int l, int r) {
        return Get(r) - ((l >= 0) ? Get(l - 1) : T(0));
    }
};

template <class T>
T invGeneral(T a, T b) {
    a %= b;
    if (!a) return b == 1 ? 0 : -1;
    T x = invGeneral(b, a);
    return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int k, m, n;
    cin >> k >> m >> n;

    vector<uint64_t> pw(n + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * base;
    uint64_t offset = accumulate(pw.begin(), pw.begin() + k, uint64_t(0));

    vector<uint64_t> hash(m);
    Vec<2, int> a(m, k);
    for (int i = 0; i < m; i++) {
        vector<int> p(n);
        for (int j = 0; j < k; j++) {
            cin >> a[i][j];
            a[i][j]--;
            p[a[i][j]] = j;
        }
        for (int j = 0; j < k; j++) {
            hash[i] += pw[j] * (p[j] + 1);
        }
    }

    vector<int> b(n);
    for (int i = 0; i < n; i++) cin >> b[i];
    auto c = b;
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    for (int i = 0; i < n; i++) {
        b[i] = lower_bound(c.begin(), c.end(), b[i]) - c.begin() + 1;
    }

    segtree_t* tree = new segtree_t(1, n);
    fenwick_t<int> cnt(n);

    const uint64_t inv_base = 13190855474080620501ULL;

    auto add = [&](int x, int p) {
        int k = cnt.Get(x);
        cnt.Update(x, 1);
        tree->Update(x, n, base);
        tree->Update(x, uint64_t(p + 1) * pw[k]);
    };

    auto del = [&](int x) {
        cnt.Update(x, -1);
        tree->Update(x, n, inv_base);
        tree->Update(x, 0);
    };

    map<uint64_t, int> trace;
    for (int i = 0; i < m; i++) {
        trace[hash[i]] = i;
    }

    bool good = 0;

    for (int i = 0; i < n; i++) {
        add(b[i], i);
        if (i >= k) {
            del(b[i - k]);
        }
        if (i >= k - 1) {
            uint64_t cur = tree->val - offset * uint64_t(i - k + 1);
            if (trace.count(cur)) {
                int j = trace[cur];
                for (auto&& x : a[j]) cout << x + 1 << ' ';
                return 0;
            }
        }
    }
    cout << 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 3628kb

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

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: 592ms
memory: 148252kb

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: 1911ms
memory: 148064kb

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: 579ms
memory: 148032kb

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: 1905ms
memory: 148072kb

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: 1938ms
memory: 148132kb

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: 1817ms
memory: 148188kb

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: 1824ms
memory: 148040kb

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: 1786ms
memory: 148068kb

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: 1764ms
memory: 148028kb

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: 457ms
memory: 148124kb

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: 447ms
memory: 148072kb

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: 602ms
memory: 148084kb

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: 1807ms
memory: 148020kb

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: 503ms
memory: 148028kb

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: 705ms
memory: 148124kb

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: 710ms
memory: 148252kb

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: 1802ms
memory: 148056kb

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: 1812ms
memory: 148052kb

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: -100
Time Limit Exceeded

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:


result: