Submission #74279318

---

Source Code Expand

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

using ll = long long;
using i64 = long long;
using i128 = __int128;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<std::pair<int, int>, null_type, less<std::pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_pair;

typedef tree<i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_64;
typedef tree<std::pair<i64, i64>, null_type, less<std::pair<i64, i64>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_pair_64;

std::istream& operator>>(std::istream& iss, i128& n) {
    std::string s;
    iss >> s;
    n = 0;

    for (int i = (s[0] == '-'); i < s.size(); i++) {
        n = n * 10 + (s[i] - '0');
    }

    if (s[0] == '-') n = -n;
    return iss;
}

std::ostream& operator<<(std::ostream& oss, i128 n) {
    if (n == 0) return oss << "0";

    std::string s;
    if (n < 0) {
        s += '-';
        n = -n;
    }

    while (n) {
        s += '0' + n % 10;
        n /= 10;
    }

    std::reverse(s.begin() + (s[0] == '-'), s.end());
    return oss << s;
}

static const long long pow2[] = { 
    1LL, 2LL, 4LL, 8LL, 16LL, 32LL, 64LL, 128LL, 256LL, 512LL, 1024LL, 2048LL, 4096LL, 8192LL, 16384LL, 32768LL, 65536LL, 131072LL, 262144LL, 524288LL, 1048576LL, 2097152LL, 4194304LL, 8388608LL, 16777216LL, 33554432LL, 67108864LL, 134217728LL, 268435456LL, 536870912LL, 1073741824LL, 2147483648LL, 4294967296LL, 8589934592LL, 17179869184LL, 34359738368LL, 68719476736LL, 137438953472LL, 274877906944LL, 549755813888LL, 1099511627776LL, 2199023255552LL, 4398046511104LL, 8796093022208LL, 17592186044416LL, 35184372088832LL, 70368744177664LL, 140737488355328LL, 281474976710656LL, 562949953421312LL, 1125899906842624LL, 2251799813685248LL, 4503599627370496LL, 9007199254740992LL, 18014398509481984LL, 36028797018963968LL, 72057594037927936LL, 144115188075855872LL, 288230376151711744LL, 576460752303423488LL
};
static const long long pow3[] = {
    1LL, 3LL, 9LL, 27LL, 81LL, 243LL, 729LL, 2187LL, 6561LL, 19683LL, 59049LL, 177147LL, 531441LL, 1594323LL, 4782969LL, 14348907LL, 43046721LL, 129140163LL, 387420489LL, 1162261467LL, 3486784401LL, 10460353203LL, 31381059609LL, 94143178827LL, 282429536481LL, 847288609443LL, 2541865828329LL, 7625597484987LL, 22876792454961LL, 68630377364883LL, 205891132094649LL, 617673396283947LL, 1853020188851841LL, 5559060566555523LL, 16677181699666569LL, 50031545098999707LL, 150094635296999121LL, 450283905890997363LL
};
static const long long pow5[] = {
    1LL, 5LL, 25LL, 125LL, 625LL, 3125LL, 15625LL, 78125LL, 390625LL, 1953125LL, 9765625LL, 48828125LL, 244140625LL, 1220703125LL, 6103515625LL, 30517578125LL, 152587890625LL, 762939453125LL, 3814697265625LL, 19073486328125LL, 95367431640625LL, 476837158203125LL, 2384185791015625LL, 11920928955078125LL, 59604644775390625LL, 298023223876953125LL, 1490116119384765625LL
};
static const long long pow10[] = {
    1LL, 10LL, 100LL, 1000LL, 10000LL, 100000LL, 1000000LL, 10000000LL, 100000000LL, 1000000000LL, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL, 1000000000000000000LL
};

const i64 MOD1 = 1e9 + 7;
const i64 MOD2 = 998244353;
const i64 LARGE = 1e17;

void cf(bool value) {
    if (value) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

void atc(bool value) {
    if (value) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
}

/**
 * usage:
 * unordered_set<i64, custom_hash>
 * unordered_map<i64, i64, custom_hash>
 * // problem: https://atcoder.jp/contests/abc448/tasks/abc448_d
 */
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t RANDOM =
            std::chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + RANDOM);
    }
};

/**
 * usage:
 * unordered_set<pair<i64, i64>, pair_hash<i64, i64>>
 */
template<class T, class U>
struct pair_hash {
    size_t operator()(const std::pair<T,U>& p) const {
        uint64_t h1 = custom_hash::splitmix64((uint64_t)p.first);
        uint64_t h2 = custom_hash::splitmix64((uint64_t)p.second);
        return custom_hash::splitmix64(h1 ^ (h2 << 1));
    }
};

/**
 * usage:
 * unordered_set<vector<i64>, vector_hash<i64>>
 * // problem: https://codeforces.com/contest/1980/problem/E
 * 
 * unordered_map<vector<int>, int, vector_hash<int>>
 * // problem: https://atcoder.jp/contests/abc361/tasks/abc361_d
 */

template<class T>
struct vector_hash {
    size_t operator()(const std::vector<T>& v) const {
        static const uint64_t RANDOM =
            std::chrono::steady_clock::now().time_since_epoch().count();

        uint64_t h = RANDOM;
        for (auto &x : v) {
            uint64_t y = custom_hash::splitmix64((uint64_t)x);
            h = custom_hash::splitmix64(h ^ y);
        }

        return h;
    }
};

/**
 * usage:
 * unordered_set<tuple<int,int,int>, tuple_hash>
 */
struct tuple_hash {
    template<class... T>
    size_t operator()(const std::tuple<T...>& t) const {
        return apply([](const auto&... args) {
            uint64_t h = 0;
            ((h = custom_hash::splitmix64(h ^
                custom_hash::splitmix64((uint64_t)args))), ...);
            return h;
        }, t);
    }
};

struct DSU {
    std::vector<i64> par, sz, color;

    // 1-based indexing
    DSU(i64 n) {
        par.resize(n + 1, 0LL); 
        sz.resize(n + 1, 1LL);
        color.resize(n + 1, 0LL);
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            color[i] = i;
        }
    }

    // find the parent of x's component
    i64 find(i64 x) {
        while (x != par[x]) {
            x = par[x] = par[par[x]];
        }
        return x;
    }

    // to get the size of component x belongs to
    i64 size(i64 x) {
        x = find(x);
        return sz[x];
    }

    // check if x and y are in same component
    bool same(i64 x, i64 y) {
        return find(x) == find(y);
    }

    // merge components of x and y
    bool merge(i64 x, i64 y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) std::swap(x, y);
        par[y] = x;
        sz[x] += sz[y];
        return true;
    }

    bool merge_without_swap(i64 x, i64 y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        par[y] = x;
        sz[x] += sz[y];
        return true;
    }
};

const i64 SIEVE_MAX = 1e9;
const i64 SIEVE_SQRT = 1e6;
 
i64 lp[SIEVE_SQRT + 1];
std::vector<i64> prs;
 
void init_sieve() {
    for (i64 i = 2; i <= SIEVE_SQRT; i++) {
        if (lp[i] == 0) {
            lp[i] = i;
            prs.push_back(i);
        }
        for (i64 j = 0; i * prs[j] <= SIEVE_SQRT; j++) {
            lp[i * prs[j]] = prs[j];
            if (prs[j] == lp[i]) break;
        }
    }
}
 
i64 binpow(i64 x, i64 y,i64 m) {
    x %= m;
    i64 result = 1;
 
    while (y > 0) {
        if (y & 1) result = result * x % m;
        x = x * x % m;
        y >>= 1;
    }
 
    result %= m;
    return result;
}
 
i64 modinv(i64 x, i64 p) {
    return binpow(x, p - 2, p);
}

struct Pascal {
    i64 N, M = -1;
    std::vector<std::vector<i64>> binom;

    Pascal(i64 N, i64 M = -1): N(N), M(M) {
        binom.resize(N + 1, std::vector<i64>(N + 1));
        compute();
    }

    void compute() {
        for (int i = 0; i <= N; i++) {
            binom[i][0] = 1;
            binom[i][i] = 1;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j < i; j++) {
                i64 ans = binom[i - 1][j] + binom[i - 1][j - 1];
                if (M != -1) ans %= M;
                binom[i][j] = ans;
            }
        }
    }   

    i64 C(i64 n, i64 k) {
        if (k < 0 || k > n) return 0;
        return binom[n][k];
    }
};

struct TrieNode {
    i64 count;
    TrieNode* link[26];
    TrieNode() {
        count = 0LL;
        for (int i = 0; i < 26; i++) {
            link[i] = nullptr;
        }
    }
};

struct Trie {
    TrieNode* root;
    Trie() {
        root = new TrieNode();
    }

    i64 add(std::string s) {
        i64 ans = 0;
        TrieNode* new_root = root;
        for (int i = 0; i < s.length(); i++) {
            if (new_root->link[s[i] - 'a'] == nullptr) {
                new_root->link[s[i] - 'a'] = new TrieNode();
            }
            new_root = new_root->link[s[i] - 'a'];
            ans += new_root->count;
            new_root->count++;
        }
        return ans;
    }
};

i64 isqrt(i64 x) {
    i64 r = sqrtl(x);
    while ((r + 1) * (r + 1) <= x) r++;
    while (r * r > x) r--;
    return r;
}

struct binomial {
    void copy() {
        i64 n;
        i64 fact[n + 1], invfact[n + 1];
        fact[0] = 1; invfact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (i * fact[i - 1]) % MOD2;
        }

        invfact[n] = modinv(fact[n], MOD2);
        for (int i = n - 1; i > 0; i--) {
            invfact[i] = (invfact[i + 1] * (i + 1)) % MOD2;
        }

        auto coeff = [&] (i64 x, i64 y) -> i64 {
            if (x < y || y < 0) return 0;
            i64 ans = 1;
            ans = (ans * fact[x]) % MOD2;
            ans = (ans * invfact[y]) % MOD2;
            ans = (ans * invfact[x - y]) % MOD2;
            return ans;
        };
    }
};

struct MergeSortTree {
    struct MergeSortNode {
        vector<i64> sorted; // sorted by x
        vector<i64> suff; // suff minima of y
    };

    i64 n;
    vector<MergeSortNode> a;
    MergeSortTree(i64 n, vector<i64>& tin, vector<i64>& tout): n(n) {
        a.resize(4 * n + 5);
        build_tree(tin, tout, 1, 1, n);
    }

    MergeSortNode combine(MergeSortNode n1, MergeSortNode n2) {
        MergeSortNode res;
        i64 l = 0, r = 0;
        while (l < n1.sorted.size() && r < n2.sorted.size()) {
            if (n1.sorted[l] < n2.sorted[r]) {
                res.sorted.push_back(n1.sorted[l++]);
            } else {
                res.sorted.push_back(n2.sorted[r++]);
            }
        }

        while (l < n1.sorted.size()) res.sorted.push_back(n1.sorted[l++]);
        while (r < n2.sorted.size()) res.sorted.push_back(n2.sorted[r++]);

        i64 len = res.sorted.size();
        res.suff.resize(len);
        res.suff[len - 1] = res.sorted[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            res.suff[i] = min(res.suff[i + 1], res.sorted[i]);
        }
        return res;
    }

    void build_tree(vector<i64>& tin, vector<i64>& tout, i64 v, i64 l, i64 r) {
        if (l == r) {
            a[v].sorted.push_back(tin[l]);
            a[v].suff.push_back(tout[l]);
            return;
        }

        i64 mid = (l + r) >> 1;
        build_tree(tin, tout, 2 * v, l, mid);
        build_tree(tin, tout, 2 * v + 1, mid + 1, r);
        a[v] = combine(a[2 * v], a[2 * v + 1]);
    }

    bool exists(MergeSortNode& res, i64 x, i64 y) {
        auto it = lower_bound(res.sorted.begin(), res.sorted.end(), x);
        if (it == res.sorted.end()) return false;

        i64 pos = it - res.sorted.begin();
        return res.suff[pos] <= y;
    }

    bool check(i64 x, i64 y, i64 l, i64 r, i64 v, i64 L, i64 R) {
        if (L > R || L > r || R < l) return false;
        if (l <= L && R <= r) {
            return exists(a[v], x, y);
        }

        i64 mid = (L + R) >> 1;
        if (check(x, y, l, r, 2 * v, L, mid)) return true;
        if (check(x, y, l, r, 2 * v + 1, mid + 1, R)) return true;
        return false;
    }

    bool check(i64 x, i64 y, i64 l, i64 r) {
        return check(x, y, l, r, 1, 1, n);
    }
};

struct Node {
    i64 val;
    Node(i64 v = 0): val(v) {}
    Node& operator=(i64 v) {
        val = v;
        return *this;
    }
    Node& operator+=(i64 v) {
        val += v;
        return *this;
    }
    Node& operator+=(const Node& other) {
        val += other.val;
        return *this;
    }
};

template <typename Merge>
struct IterativeSegtree {
    i64 N;
    vector<Node> tree;
    Merge merge;
    Node identity;

    IterativeSegtree(i64 n, const vector<i64>& a,
                    Merge merge,
                    Node identity): N(n), merge(merge), identity(identity) {
        tree.assign(2 * N, identity);
        construct(a);
    }

    void construct(const vector<i64>& a) {
        for (int i = 1; i <= N; i++) tree[i + N - 1] = a[i];
        for (int i = N - 1; i >= 1; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
    }

    // answer sum a[l, r)
    i64 query(i64 l, i64 r) {
        Node resl = identity, resr = identity;
        for (l += N - 1, r += N - 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tree[l++]);
            if (r & 1) resr = merge(tree[--r], resr);
        }
        return merge(resl, resr).val;
    }

    // set a[idx] = val
    void set(i64 idx, i64 val) {
        idx += N - 1;
        tree[idx] = val;
        for (idx >>= 1; idx > 0; idx >>= 1) {
            tree[idx] = merge(tree[idx << 1], tree[idx << 1 | 1]);
        }
    }

    // update a[idx] += val
    void update(i64 idx, i64 val) {
        idx += N - 1;
        tree[idx] += val;
        for (idx >>= 1; idx > 0; idx >>= 1) {
            tree[idx] = merge(tree[idx << 1], tree[idx << 1 | 1]);
        }
    }
};

// IterativeSegtree<RangeSum> tree(n, a, RangeSum(), Node(0));
struct RangeSum {
    Node operator()(const Node& a, const Node& b) const {
        return Node(a.val + b.val);
    }
};

// IterativeSegtree<RangeMin> tree(n, a, RangeMin(), Node(2e18));
struct RangeMin {
    Node operator()(const Node& a, const Node& b) const {
        return Node(min(a.val, b.val));
    }
};

// IterativeSegtree<RangeMax> tree(n, a, RangeMax(), Node(-2e18));
struct RangeMax {
    Node operator()(const Node& a, const Node& b) const {
        return Node(max(a.val, b.val));
    };
};

void solve() {
    i64 n, k;
    cin >> n >> k;
    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= k;
    }

    if (n == 1) {
        cout << 0 << '\n';
        return;
    }

    sort(a.begin() + 1, a.end());
    i64 best = LLONG_MAX;
    a[0] = a[n] - k;
    for (int i = 1; i <= n; i++) {
        best = min(best, k + a[i - 1] - a[i]);
    }

    cout << best << '\n';
}   

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t;

    // preprocessing
    // init_sieve();

    bool debug = true;
    if (true) {
        while (t--) {
            solve();
        }
    } else {
        vector<pair<pair<i64, i64>, vector<i64>>> tests;
        for (int i = 0; i < t; i++) {
            i64 x, y;
            cin >> x >> y;
            pair<i64, i64> p = {x, y};
            vector<i64> a;
            for (int j = 1; j <= x; j++) {
                i64 z; cin >> z;
                a.push_back(z);
            }
            tests.push_back({p, a});
        }

        cout << tests[39].first.first << ' ' << tests[39].first.second << '\n';
        for (auto u: tests[39].second) {
            cout << u << ' ';
        }
    }
}

Submission Info

Compile Error

./Main.cpp: In function 'std::istream& operator>>(std::istream&, i128&)':
./Main.cpp:24:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = (s[0] == '-'); i < s.size(); i++) {
      |                                 ~~^~~~~~~~~~
./Main.cpp: In member function 'i64 Trie::add(std::string)':
./Main.cpp:297:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  297 |         for (int i = 0; i < s.length(); i++) {
      |                         ~~^~~~~~~~~~~~
./Main.cpp: In member function 'void binomial::copy()':
./Main.cpp:330:14: warning: variable 'coeff' set but not used [-Wunused-but-set-variable]
  330 |         auto coeff = [&] (i64 x, i64 y) -> i64 {
      |              ^~~~~
./Main.cpp: In member function 'MergeSortTree::MergeSortNode MergeSortTree::combine(MergeSortNode, MergeSortNode)':
./Main.cpp:357:18: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  357 |         while (l < n1.sorted.size() && r < n2.sorted.size()) {
      |                ~~^~~~~~~~~~~~~~~~~~
./Main.cpp:357:42: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  357 |         while (l < n1.sorted.size() && r < n2.sorted.size()) {
      |                                        ~~^~~~~~~~~~~~~~~~~~
./Main.cpp:365:18: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  365 |         while (l < n1.sorted.size()) res.sorted.push_back(n1.sorted[l++]);
      |                ~~^~~~~~~~~~~~~~~~~~
./Main.cpp:366:18: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  366 |         while (r < n2.sorted.size()) res.sorted.push_back(n2.sorted[r++]);
      |                ~~^~~~~~~~~~~~~~~~~~
./Main.cpp: In function 'int main()':
./Main.cpp:535:10: warning: unused variable 'debug' [-Wunused-variable]
  535 |     bool debug = true;
      |          ^~~~~

Judge Result