QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#304611 | #8008. Fortune Wheel | ucup-team112# | WA | 114ms | 4712kb | C++20 | 14.3kb | 2024-01-13 21:48:58 | 2024-01-13 21:48:58 |
Judging History
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) {
vec(bool, used, n, false);
fori(i, n) {
if (used[i]) continue;
vec(int, inds, 0);
int j = i;
while (!used[j]) {
inds.push_back(j);
used[j] = true;
j = (j + a) % n;
}
int bj = inds.back();
fori(2) {
for (auto j : inds) {
chmin(dp[j], dp[bj] + 1);
bj = j;
}
}
}
}
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: 3604kb
input:
6 3 2 2 4
output:
8 3
result:
ok 2 number(s): "8 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
5 4 1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 114ms
memory: 4712kb
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: 0
Accepted
time: 0ms
memory: 3780kb
input:
10000 23 7 9594 8998 9330 6851 1662 6719 583
output:
42726 4805
result:
ok 2 number(s): "42726 4805"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
100 3 100 7 68 28 98 19 32 90 79 92 40 96 30 95 91 71 15 33 18 69 1 61 43 5 75 73 64 58 100 88 20 99 37 17 22 82 67 70 55 47 80 66 12 4 24 26 54 74 57 21 77 86 89 83 29 46 31 2 16 49 48 25 93 52 9 85 84 42 39 8 65 10 45 63 87 78 60 23 14 34 59 81 38 41 76 3 13 27 36 35 51 44 62 53 94 6 50 11 97 72 56
output:
1 1
result:
ok 2 number(s): "1 1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
100 93 4 63 58 3 89
output:
19 4
result:
ok 2 number(s): "19 4"
Test #7:
score: 0
Accepted
time: 6ms
memory: 4512kb
input:
75057 45721 3 10861 27551 14278
output:
32797 933
result:
ok 2 number(s): "32797 933"
Test #8:
score: 0
Accepted
time: 7ms
memory: 4652kb
input:
97777 94043 1 83579
output:
97619 221
result:
ok 2 number(s): "97619 221"
Test #9:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
13515 10596 5 11890 9097 4596 13464 13309
output:
6022 489
result:
ok 2 number(s): "6022 489"
Test #10:
score: 0
Accepted
time: 6ms
memory: 4416kb
input:
77777 64477 3 45863 40922 74543
output:
298537 8416
result:
ok 2 number(s): "298537 8416"
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3524kb
input:
1 0 1 1
output:
0
result:
wrong answer Answer contains longer sequence [length = 2], but output contains 1 elements