QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#304609#8008. Fortune Wheelucup-team112#WA 121ms3956kbC++2013.8kb2024-01-13 21:46:142024-01-13 21:46:15

Judging History

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

  • [2024-07-30 15:38:33]
  • hack成功,自动添加数据
  • (/hack/759)
  • [2024-07-10 08:02:33]
  • hack成功,自动添加数据
  • (/hack/730)
  • [2024-01-13 21:46:15]
  • 评测
  • 测评结果:WA
  • 用时:121ms
  • 内存:3956kb
  • [2024-01-13 21:46:14]
  • 提交

answer

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

namespace templates {
// type
using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pil = pair<int, ll>;
using Pli = pair<ll, int>;
using Pll = pair<ll, ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using qp = priority_queue<T, vector<T>, greater<T>>;
// clang-format off
#define vec(T, A, ...) vector<T> A(__VA_ARGS__);
#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));
#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));
// clang-format on

// for loop
#define fori1(a) for (ll _ = 0; _ < (a); _++)
#define fori2(i, a) for (ll i = 0; i < (a); i++)
#define fori3(i, a, b) for (ll i = (a); i < (b); i++)
#define fori4(i, a, b, c) for (ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)

// declare and input
// clang-format off
#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);
#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);
#define DOUBLE(...) double __VA_ARGS__; STRING(str___); __VA_ARGS__ = stod(str___);
#define VEC(T, A, n) vector<T> A(n); inp(A);
#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);
// clang-format on

// const value
const ll MOD1   = 1000000007;
const ll MOD9   = 998244353;
const double PI = acos(-1);

// other macro
#ifndef RIN__LOCAL
#define endl "\n"
#endif
#define spa ' '
#define len(A) ll(A.size())
#define all(A) begin(A), end(A)

// function
vector<char> stoc(string &S) {
    int n = S.size();
    vector<char> ret(n);
    for (int i = 0; i < n; i++) ret[i] = S[i];
    return ret;
}
string ctos(vector<char> &S) {
    int n      = S.size();
    string ret = "";
    for (int i = 0; i < n; i++) ret += S[i];
    return ret;
}

template <class T>
auto min(const T &a) {
    return *min_element(all(a));
}
template <class T>
auto max(const T &a) {
    return *max_element(all(a));
}
template <class T, class S>
auto clamp(T &a, const S &l, const S &r) {
    return (a > r ? r : a < l ? l : a);
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chclamp(T &a, const S &l, const S &r) {
    auto b = clamp(a, l, r);
    return (a != b ? a = b, 1 : 0);
}

template <typename T>
T sum(vector<T> &A) {
    T tot = 0;
    for (auto a : A) tot += a;
    return tot;
}

template <typename T>
vector<T> compression(vector<T> X) {
    sort(all(X));
    X.erase(unique(all(X)), X.end());
    return X;
}

// input and output
namespace io {

// vector<T>
template <typename T>
istream &operator>>(istream &is, vector<T> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << ' ';
    }
    return os;
}

// vector<vector<T>>
template <typename T>
istream &operator>>(istream &is, vector<vector<T>> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<vector<T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}

// pair<S, T>
template <typename S, typename T>
istream &operator>>(istream &is, pair<S, T> &A) {
    is >> A.first >> A.second;
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, pair<S, T> &A) {
    os << A.first << ' ' << A.second;
    return os;
}

// vector<pair<S, T>>
template <typename S, typename T>
istream &operator>>(istream &is, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        is >> A[i];
    }
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}

// tuple
template <typename T, size_t N>
struct TuplePrint {
    static ostream &print(ostream &os, const T &t) {
        TuplePrint<T, N - 1>::print(os, t);
        os << ' ' << get<N - 1>(t);
        return os;
    }
};
template <typename T>
struct TuplePrint<T, 1> {
    static ostream &print(ostream &os, const T &t) {
        os << get<0>(t);
        return os;
    }
};
template <typename... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t) {
    TuplePrint<decltype(t), sizeof...(Args)>::print(os, t);
    return os;
}

// io functions
void FLUSH() {
    cout << flush;
}

void print() {
    cout << endl;
}
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
    cout << head;
    if (sizeof...(Tail)) cout << spa;
    print(std::forward<Tail>(tail)...);
}

template <typename T, typename S>
void prisep(vector<T> &A, S sep) {
    int n = A.size();
    for (int i = 0; i < n; i++) {
        cout << A[i];
        if (i != n - 1) cout << sep;
    }
    cout << endl;
}
template <typename T, typename S>
void priend(T A, S end) {
    cout << A << end;
}
template <typename T>
void prispa(T A) {
    priend(A, spa);
}
template <typename T, typename S>
bool printif(bool f, T A, S B) {
    if (f)
        print(A);
    else
        print(B);
    return f;
}

template <class... T>
void inp(T &...a) {
    (cin >> ... >> a);
}

} // namespace io
using namespace io;

// read graph
vector<vector<int>> read_edges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<int>> edges(n, vector<int>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        u -= indexed;
        v -= indexed;
        edges[u].push_back(v);
        if (!direct) edges[v].push_back(u);
    }
    return edges;
}
vector<vector<int>> read_tree(int n, int indexed = 1) {
    return read_edges(n, n - 1, false, indexed);
}

template <typename T = long long>
vector<vector<pair<int, T>>> read_wedges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<pair<int, T>>> edges(n, vector<pair<int, T>>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        T w;
        inp(w);
        u -= indexed;
        v -= indexed;
        edges[u].push_back({v, w});
        if (!direct) edges[v].push_back({u, w});
    }
    return edges;
}
template <typename T = long long>
vector<vector<pair<int, T>>> read_wtree(int n, int indexed = 1) {
    return read_wedges<T>(n, n - 1, false, indexed);
}

// yes / no
namespace yesno {

// yes
inline bool yes(bool f = true) {
    cout << (f ? "yes" : "no") << endl;
    return f;
}
inline bool Yes(bool f = true) {
    cout << (f ? "Yes" : "No") << endl;
    return f;
}
inline bool YES(bool f = true) {
    cout << (f ? "YES" : "NO") << endl;
    return f;
}

// no
inline bool no(bool f = true) {
    cout << (!f ? "yes" : "no") << endl;
    return f;
}
inline bool No(bool f = true) {
    cout << (!f ? "Yes" : "No") << endl;
    return f;
}
inline bool NO(bool f = true) {
    cout << (!f ? "YES" : "NO") << endl;
    return f;
}

// possible
inline bool possible(bool f = true) {
    cout << (f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Possible(bool f = true) {
    cout << (f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool POSSIBLE(bool f = true) {
    cout << (f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}

// impossible
inline bool impossible(bool f = true) {
    cout << (!f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Impossible(bool f = true) {
    cout << (!f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool IMPOSSIBLE(bool f = true) {
    cout << (!f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}

// Alice Bob
inline bool Alice(bool f = true) {
    cout << (f ? "Alice" : "Bob") << endl;
    return f;
}
inline bool Bob(bool f = true) {
    cout << (f ? "Bob" : "Alice") << endl;
    return f;
}

// Takahashi Aoki
inline bool Takahashi(bool f = true) {
    cout << (f ? "Takahashi" : "Aoki") << endl;
    return f;
}
inline bool Aoki(bool f = true) {
    cout << (f ? "Aoki" : "Takahashi") << endl;
    return f;
}

} // namespace yesno
using namespace yesno;

} // namespace templates
using namespace templates;

template <typename T>
T modinv(T a, T MOD) {
    T b = MOD;
    T u = 1;
    T v = 0;
    while (b > 0) {
        T t = a / b;
        a -= t * b;
        u -= t * v;
        std::swap(a, b);
        std::swap(u, v);
    }
    if (a != 1) return -1;
    if (u < 0) u += MOD;
    return u;
}

struct Fraction {
    long long nume, deno;
    Fraction() : nume(0), deno(1) {}
    Fraction(long long nume) : nume(nume), deno(1) {}
    Fraction(long long nume_, long long deno_) {
        assert(deno_ != 0);
        nume = nume_;
        deno = deno_;
        // long long g = std::gcd(nume_, deno_);
        // nume        = nume_ / g;
        // deno        = deno_ / g;
    }

    Fraction &operator+=(const Fraction &p) {
        long long g = std::gcd(deno, p.deno);
        long long d = deno / g * p.deno;
        long long n = p.deno / g * nume + deno / g * p.nume;
        g           = std::gcd(d, n);
        nume        = n / g;
        deno        = d / g;
        return *this;
    }

    Fraction &operator-=(const Fraction &p) {
        long long g = std::gcd(deno, p.deno);
        long long d = deno / g * p.deno;
        long long n = p.deno / g * nume - deno / g * p.nume;
        g           = std::gcd(d, n);
        nume        = n / g;
        deno        = d / g;
        return *this;
    }

    Fraction &operator*=(const Fraction &p) {
        long long g1 = std::gcd(deno, p.nume);
        long long g2 = std::gcd(nume, p.deno);
        long long d  = (deno / g1) * (p.deno / g2);
        long long n  = (p.nume / g1) * (nume / g2);
        nume         = n;
        deno         = d;
        return *this;
    }

    Fraction &operator/=(const Fraction &p) {
        assert(p.nume != 0);
        *this *= p.inv();
        return *this;
    }

    Fraction operator-() const {
        return Fraction(-nume, deno);
    }

    Fraction &operator++() {
        nume += deno;
        return *this;
    }

    Fraction &operator--() {
        nume -= deno;
        return *this;
    }

    Fraction operator++(int) {
        Fraction result = *this;
        ++*this;
        return result;
    }

    Fraction operator--(int) {
        Fraction result = *this;
        --*this;
        return result;
    }

    friend Fraction operator+(const Fraction &lhs, const Fraction &rhs) {
        return Fraction(lhs) += rhs;
    }

    friend Fraction operator-(const Fraction &lhs, const Fraction &rhs) {
        return Fraction(lhs) -= rhs;
    }

    friend Fraction operator*(const Fraction &lhs, const Fraction &rhs) {
        return Fraction(lhs) *= rhs;
    }

    friend Fraction operator/(const Fraction &lhs, const Fraction &rhs) {
        return Fraction(lhs) /= rhs;
    }

    bool operator==(const Fraction &p) const {
        return (nume == p.nume && deno == p.deno);
    }

    bool operator!=(const Fraction &p) const {
        return (nume != p.nume || deno != p.deno);
    }

    bool operator<(const Fraction &p) const {
        return nume * p.deno < deno * p.nume;
    }

    bool operator<=(const Fraction &p) const {
        return nume * p.deno <= deno * p.nume;
    }

    bool operator>(const Fraction &p) const {
        return nume * p.deno > deno * p.nume;
    }

    bool operator>=(const Fraction &p) const {
        return nume * p.deno >= deno * p.nume;
    }

    long long mod_expression(long long MOD) {
        assert(std::gcd(deno, MOD) == 1);
        return nume * modinv(deno, MOD) % MOD;
    }

    Fraction inv() const {
        return Fraction(deno, nume);
    }

    friend std::ostream &operator<<(std::ostream &os, const Fraction &p) {
        return os << p.nume << '/' << p.deno;
    }

    friend std::istream &operator>>(std::istream &is, Fraction &p) {
        long long y;
        is >> y;
        p = Fraction(y);
        return (is);
    }

    Fraction pow(int64_t k) const {
        Fraction ret(1);
        Fraction y(nume, deno);
        while (k > 0) {
            if (k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }
};

void solve() {
    LL(n, x, K);
    VEC(ll, A, K);
    if (x == 0) {
        print(0);
        return;
    }
    x            = n - x;
    const ll inf = 1 << 20;
    vec(ll, dp, n, inf);
    dp[0] = 0;
    for (auto a : A) {
        fori(i, 2 * n) {
            chmin(dp[(i + a) % n], dp[i % n] + 1);
        }
    }
    Fraction ans(dp[x]);
    sort(all(dp));
    ll tot = 0;
    for (auto d : dp) {
        if (d != inf) tot += d;
    }
    fori(i, n - 1, -1, -1) {
        if (dp[i] == inf) continue;
        Fraction f = Fraction(tot + n, i + 1);
        if (f < ans) ans = f;
        tot -= dp[i];
    }
    ll p = ans.nume;
    ll q = ans.deno;
    ll g = std::gcd(p, q);
    p /= g;
    q /= g;
    print(p, q);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    // cout << fixed << setprecision(12);
    int t;
    t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6 3 2
2 4

output:

8 3

result:

ok 2 number(s): "8 3"

Test #2:

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

input:

5 4 1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

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

input:

99999 65238 100
64714 45675 36156 13116 93455 22785 10977 60219 14981 25839 83709 80404 41400 12469 31530 65521 35436 20326 96792 50699 27522 98233 26187 12509 90992 72693 83919 74145 80892 68422 38333 33497 89154 88403 77492 4570 3908 59194 3482 89871 96330 45114 5555 73987 95832 476 949 74649 2084...

output:

3 1

result:

ok 2 number(s): "3 1"

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 3680kb

input:

10000 23 7
9594 8998 9330 6851 1662 6719 583

output:

7124 751

result:

wrong answer 1st numbers differ - expected: '42726', found: '7124'