QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#309016 | #8135. Minimum Cost Flow² | ucup-team180# | AC ✓ | 71ms | 70060kb | C++20 | 48.6kb | 2024-01-20 14:13:50 | 2024-01-20 14:13:50 |
Judging History
answer
#pragma region Macros
#ifdef noimi
#include "my_template.hpp"
#else
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <immintrin.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <immintrin.h>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#ifdef noimi
#define oj_local(a, b) b
#else
#define oj_local(a, b) a
#endif
#define LOCAL if(oj_local(0, 1))
#define OJ if(oj_local(1, 0))
using namespace std;
using ll = long long;
using ull = unsigned long long int;
using i128 = __int128_t;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vc<T>>;
template <typename T> using vvvc = vector<vvc<T>>;
using vi = vc<int>;
using vl = vc<ll>;
using vpi = vc<pii>;
using vpl = vc<pll>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T> int si(const T &x) { return x.size(); }
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); }
vi iota(int n) {
vi a(n);
return iota(a.begin(), a.end(), 0), a;
}
template <typename T> vi iota(const vector<T> &a, bool greater = false) {
vi res(a.size());
iota(res.begin(), res.end(), 0);
sort(res.begin(), res.end(), [&](int i, int j) {
if(greater) return a[i] > a[j];
return a[i] < a[j];
});
return res;
}
// macros
#define overload5(a, b, c, d, e, name, ...) name
#define overload4(a, b, c, d, name, ...) name
#define endl '\n'
#define REP0(n) for(ll jidlsjf = 0; jidlsjf < n; ++jidlsjf)
#define REP1(i, n) for(ll i = 0; i < (n); ++i)
#define REP2(i, a, b) for(ll i = (a); i < (b); ++i)
#define REP3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)
#define per0(n) for(int jidlsjf = 0; jidlsjf < (n); ++jidlsjf)
#define per1(i, n) for(ll i = (n)-1; i >= 0; --i)
#define per2(i, a, b) for(ll i = (a)-1; i >= b; --i)
#define per3(i, a, b, c) for(ll i = (a)-1; i >= (b); i -= (c))
#define per(...) overload4(__VA_ARGS__, per3, per2, per1, per0)(__VA_ARGS__)
#define fore0(a) rep(a.size())
#define fore1(i, a) for(auto &&i : a)
#define fore2(a, b, v) for(auto &&[a, b] : v)
#define fore3(a, b, c, v) for(auto &&[a, b, c] : v)
#define fore4(a, b, c, d, v) for(auto &&[a, b, c, d] : v)
#define fore(...) overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__)
#define setbits(j, n) for(ll iiiii = (n), j = lowbit(iiiii); iiiii; iiiii ^= 1 << j, j = lowbit(iiiii))
#define perm(v) for(bool permrepflag = true; (permrepflag ? exchange(permrepflag, false) : next_permutation(all(v)));)
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define drop(s) cout << #s << endl, exit(0)
#define si(c) (int)(c).size()
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))
#define rng(v, l, r) v.begin() + (l), v.begin() + (r)
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define SORT(v) sort(all(v))
#define REV(v) reverse(all(v))
#define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end())
template <typename T = ll, typename S> T SUM(const S &v) { return accumulate(all(v), T(0)); }
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define overload2(_1, _2, name, ...) name
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
constexpr pii dx4[4] = {pii{1, 0}, pii{0, 1}, pii{-1, 0}, pii{0, -1}};
constexpr pii dx8[8] = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
namespace yesno_impl {
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
const string firstsecond[2] = {"second", "first"};
const string FirstSecond[2] = {"Second", "First"};
const string possiblestr[2] = {"impossible", "possible"};
const string Possiblestr[2] = {"Impossible", "Possible"};
void YES(bool t = 1) { cout << YESNO[t] << endl; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << endl; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << endl; }
void no(bool t = 1) { yes(!t); }
void first(bool t = 1) { cout << firstsecond[t] << endl; }
void First(bool t = 1) { cout << FirstSecond[t] << endl; }
void possible(bool t = 1) { cout << possiblestr[t] << endl; }
void Possible(bool t = 1) { cout << Possiblestr[t] << endl; }
}; // namespace yesno_impl
using namespace yesno_impl;
#define INT(...) \
int __VA_ARGS__; \
IN(__VA_ARGS__)
#define INTd(...) \
int __VA_ARGS__; \
IN2(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
IN(__VA_ARGS__)
#define LLd(...) \
ll __VA_ARGS__; \
IN2(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
IN(__VA_ARGS__)
#define CHR(...) \
char __VA_ARGS__; \
IN(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
IN(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
IN(name)
#define VECd(type, name, size) \
vector<type> name(size); \
IN2(name)
#define VEC2(type, name1, name2, size) \
vector<type> name1(size), name2(size); \
for(int i = 0; i < size; i++) IN(name1[i], name2[i])
#define VEC2d(type, name1, name2, size) \
vector<type> name1(size), name2(size); \
for(int i = 0; i < size; i++) IN2(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, size) \
vector<type> name1(size), name2(size), name3(size); \
for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i])
#define VEC3d(type, name1, name2, name3, size) \
vector<type> name1(size), name2(size), name3(size); \
for(int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, size) \
vector<type> name1(size), name2(size), name3(size), name4(size); \
for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i], name4[i]);
#define VEC4d(type, name1, name2, name3, name4, size) \
vector<type> name1(size), name2(size), name3(size), name4(size); \
for(int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i], name4[i]);
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
IN(name)
#define VVd(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
IN2(name)
int scan() { return getchar(); }
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }
template <class T> void scan(vector<T> &);
template <class T> void scan(vector<T> &a) {
for(auto &i : a) scan(i);
}
template <class T> void scan(T &a) { cin >> a; }
void IN() {}
void IN2() {}
template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {
scan(head);
IN(tail...);
}
template <class Head, class... Tail> void IN2(Head &head, Tail &...tail) {
scan(head);
--head;
IN2(tail...);
}
template <int p = -1> void pat() {}
template <int p = -1, class Head, class... Tail> void pat(Head &h, Tail &...tail) {
h += p;
pat<p>(tail...);
}
template <typename T, typename S> T ceil(T x, S y) {
assert(y);
return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y));
}
template <typename T, typename S> T floor(T x, S y) {
assert(y);
return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));
}
template <typename T, typename S, typename U> U bigmul(const T &x, const S &y, const U &lim) { // clamp(x * y, -lim, lim)
if(x < 0 and y < 0) return bigmul(-x, -y, lim);
if(x < 0) return -bigmul(-x, y, lim);
if(y < 0) return -bigmul(x, -y, lim);
return y == 0 or x <= lim / y ? x * y : lim;
}
template <class T> T POW(T x, int n) {
T res = 1;
for(; n; n >>= 1, x *= x)
if(n & 1) res *= x;
return res;
}
template <class T, class S> T POW(T x, S n, const ll &mod) {
T res = 1;
x %= mod;
for(; n; n >>= 1, x = x * x % mod)
if(n & 1) res = res * x % mod;
return res;
}
vector<pll> factor(ll x) {
vector<pll> ans;
for(ll i = 2; i * i <= x; i++)
if(x % i == 0) {
ans.push_back({i, 1});
while((x /= i) % i == 0) ans.back().second++;
}
if(x != 1) ans.push_back({x, 1});
return ans;
}
template <class T> vector<T> divisor(T x) {
vector<T> ans;
for(T i = 1; i * i <= x; i++)
if(x % i == 0) {
ans.pb(i);
if(i * i != x) ans.pb(x / i);
}
return ans;
}
template <typename T> void zip(vector<T> &x) {
vector<T> y = x;
UNIQUE(y);
for(int i = 0; i < x.size(); ++i) { x[i] = lb(y, x[i]); }
}
template <class S> void fold_in(vector<S> &v) {}
template <typename Head, typename... Tail, class S> void fold_in(vector<S> &v, Head &&a, Tail &&...tail) {
for(auto e : a) v.emplace_back(e);
fold_in(v, tail...);
}
template <class S> void renumber(vector<S> &v) {}
template <typename Head, typename... Tail, class S> void renumber(vector<S> &v, Head &&a, Tail &&...tail) {
for(auto &&e : a) e = lb(v, e);
renumber(v, tail...);
}
template <class S, class... Args> vector<S> zip(vector<S> &head, Args &&...args) {
vector<S> v;
fold_in(v, head, args...);
sort(all(v)), v.erase(unique(all(v)), v.end());
renumber(v, head, args...);
return v;
}
template <typename S> void rearrange(const vector<S> &id) {}
template <typename S, typename T> void rearrange_exec(const vector<S> &id, vector<T> &v) {
vector<T> w(v.size());
rep(i, si(id)) w[i] = v[id[i]];
v.swap(w);
}
// 並び替える順番, 並び替える vector 達
template <typename S, typename Head, typename... Tail> void rearrange(const vector<S> &id, Head &a, Tail &...tail) {
rearrange_exec(id, a);
rearrange(id, tail...);
}
template <typename T> vector<T> RUI(const vector<T> &v) {
vector<T> res(v.size() + 1);
for(int i = 0; i < v.size(); i++) res[i + 1] = res[i] + v[i];
return res;
}
template <typename T> void zeta_supersetsum(vector<T> &f) {
int n = f.size();
for(int i = 1; i < n; i <<= 1) rep(b, n) if(!(i & b)) f[b] += f[b | i];
}
template <typename T> void zeta_subsetsum(vector<T> &f) {
int n = f.size();
for(int i = 1; i < n; i <<= 1) rep(b, n) if(!(i & b)) f[b | i] += f[b];
}
template <typename T> void mobius_subset(vector<T> &f) {
int n = f.size();
for(int i = 1; i < n; i <<= 1) rep(b, n) if(!(i & b)) f[b] -= f[b | i];
}
template <typename T> void mobius_superset(vector<T> &f) {
int n = f.size();
for(int i = 1; i < n; i <<= 1) rep(b, n) if(!(i & b)) f[b | i] -= f[b];
}
// 反時計周りに 90 度回転
template <typename T> void rot(vector<vector<T>> &v) {
if(empty(v)) return;
int n = v.size(), m = v[0].size();
vector<vector<T>> res(m, vector<T>(n));
rep(i, n) rep(j, m) res[m - 1 - j][i] = v[i][j];
v.swap(res);
}
vector<int> counter(const vector<int> &v, int max_num = -1) {
if(max_num == -1) max_num = MAX(v);
vector<int> res(max_num + 1);
fore(e, v) res[e]++;
return res;
}
// x in [l, r)
template <class T, class S> bool inc(const T &x, const S &l, const S &r) { return l <= x and x < r; }
template <class T, class S> bool inc(const T &x, const pair<S, S> &p) { return p.first <= x and x < p.second; }
// 便利関数
constexpr ll ten(int n) { return n == 0 ? 1 : ten(n - 1) * 10; }
constexpr ll tri(ll n) { return n * (n + 1) / 2; }
// l + ... + r
constexpr ll tri(ll l, ll r) { return (l + r) * (r - l + 1) / 2; }
ll max(int x, ll y) { return max((ll)x, y); }
ll max(ll x, int y) { return max(x, (ll)y); }
int min(int x, ll y) { return min((ll)x, y); }
int min(ll x, int y) { return min(x, (ll)y); }
// bit 演算系
#define bit(i) (1LL << i) // (1 << i)
#define test(b, i) (b >> i & 1) // b の i bit 目が立っているか
ll pow2(int i) { return 1LL << i; }
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int lowbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); }
int lowbit(ll a) { return a == 0 ? 64 : __builtin_ctzll(a); }
// int allbit(int n) { return (1 << n) - 1; }
constexpr ll mask(int n) { return (1LL << n) - 1; }
// int popcount(signed t) { return __builtin_popcount(t); }
// int popcount(ll t) { return __builtin_popcountll(t); }
int popcount(uint64_t t) { return __builtin_popcountll(t); }
static inline uint64_t popcount64(uint64_t x) {
uint64_t m1 = 0x5555555555555555ll;
uint64_t m2 = 0x3333333333333333ll;
uint64_t m4 = 0x0F0F0F0F0F0F0F0Fll;
uint64_t h01 = 0x0101010101010101ll;
x -= (x >> 1) & m1;
x = (x & m2) + ((x >> 2) & m2);
x = (x + (x >> 4)) & m4;
return (x * h01) >> 56;
}
bool ispow2(int i) { return i && (i & -i) == i; }
ll rnd(ll l, ll r) { //[l, r)
#ifdef noimi
static mt19937_64 gen;
#else
static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
#endif
return uniform_int_distribution<ll>(l, r - 1)(gen);
}
ll rnd(ll n) { return rnd(0, n); }
template <class t> void random_shuffle(vc<t> &a) { rep(i, si(a)) swap(a[i], a[rnd(0, i + 1)]); }
int in() {
int x;
cin >> x;
return x;
}
ll lin() {
unsigned long long x;
cin >> x;
return x;
}
template <class T, class S> pair<T, S> operator-(const pair<T, S> &x) { return pair<T, S>(-x.first, -x.second); }
template <class T, class S> pair<T, S> operator-(const pair<T, S> &x, const pair<T, S> &y) { return pair<T, S>(x.fi - y.fi, x.se - y.se); }
template <class T, class S> pair<T, S> operator+(const pair<T, S> &x, const pair<T, S> &y) { return pair<T, S>(x.fi + y.fi, x.se + y.se); }
template <class T> pair<T, T> operator&(const pair<T, T> &l, const pair<T, T> &r) { return pair<T, T>(max(l.fi, r.fi), min(l.se, r.se)); }
template <class T, class S> pair<T, S> operator+=(pair<T, S> &l, const pair<T, S> &r) { return l = l + r; }
template <class T, class S> pair<T, S> operator-=(pair<T, S> &l, const pair<T, S> &r) { return l = l - r; }
template <class T> bool intersect(const pair<T, T> &l, const pair<T, T> &r) { return (l.se < r.se ? r.fi < l.se : l.fi < r.se); }
template <class T> vector<T> &operator++(vector<T> &v) {
fore(e, v) e++;
return v;
}
template <class T> vector<T> operator++(vector<T> &v, int) {
auto res = v;
fore(e, v) e++;
return res;
}
template <class T> vector<T> &operator--(vector<T> &v) {
fore(e, v) e--;
return v;
}
template <class T> vector<T> operator--(vector<T> &v, int) {
auto res = v;
fore(e, v) e--;
return res;
}
template <class T> void connect(vector<T> &l, const vector<T> &r) { fore(e, r) l.eb(e); }
template <class T> vector<T> operator+(const vector<T> &l, const vector<T> &r) {
vector<T> res(max(si(l), si(r)));
rep(i, si(l)) res[i] += l[i];
rep(i, si(r)) res[i] += r[i];
return res;
}
template <class T> vector<T> operator-(const vector<T> &l, const vector<T> &r) {
vector<T> res(max(si(l), si(r)));
rep(i, si(l)) res[i] += l[i];
rep(i, si(r)) res[i] -= r[i];
return res;
}
template <class T> vector<T> &operator+=(const vector<T> &l, const vector<T> &r) {
if(si(l) < si(r)) l.resize(si(r));
rep(i, si(r)) l[i] += r[i];
return l;
}
template <class T> vector<T> &operator-=(const vector<T> &l, const vector<T> &r) {
if(si(l) < si(r)) l.resize(si(r));
rep(i, si(r)) l[i] -= r[i];
return l;
}
template <class T> vector<T> &operator+=(vector<T> &v, const T &x) {
fore(e, v) e += x;
return v;
}
template <class T> vector<T> &operator-=(vector<T> &v, const T &x) {
fore(e, v) e -= x;
return v;
}
template <typename T> struct edge {
int from, to;
T cost;
int id;
edge(int to, T cost) : from(-1), to(to), cost(cost) {}
edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id) {}
constexpr bool operator<(const edge<T> &rhs) const noexcept { return cost < rhs.cost; }
edge &operator=(const int &x) {
to = x;
return *this;
}
operator int() const { return to; }
friend ostream operator<<(ostream &os, const edge &e) { return os << e.to; }
};
template <typename T> using Edges = vector<edge<T>>;
template <typename T = int> Edges<T> read_edges(int m, bool weighted = false) {
Edges<T> res;
res.reserve(m);
for(int i = 0; i < m; i++) {
int u, v, c = 0;
scan(u), scan(v), u--, v--;
if(weighted) scan(c);
res.eb(u, v, c, i);
}
return res;
}
using Tree = vector<vector<int>>;
using Graph = vector<vector<int>>;
template <class T> using Wgraph = vector<vector<edge<T>>>;
Graph getG(int n, int m = -1, bool directed = false, int margin = 1) {
Tree res(n);
if(m == -1) m = n - 1;
while(m--) {
int a, b;
cin >> a >> b;
a -= margin, b -= margin;
res[a].emplace_back(b);
if(!directed) res[b].emplace_back(a);
}
return res;
}
Graph getTreeFromPar(int n, int margin = 1) {
Graph res(n);
for(int i = 1; i < n; i++) {
int a;
cin >> a;
res[a - margin].emplace_back(i);
}
return res;
}
template <class T> Wgraph<T> getWg(int n, int m = -1, bool directed = false, int margin = 1) {
Wgraph<T> res(n);
if(m == -1) m = n - 1;
while(m--) {
int a, b;
T c;
scan(a), scan(b), scan(c);
a -= margin, b -= margin;
res[a].emplace_back(b, c);
if(!directed) res[b].emplace_back(a, c);
}
return res;
}
void add(Graph &G, int x, int y) { G[x].eb(y), G[y].eb(x); }
template <class S, class T> void add(Wgraph<S> &G, int x, int y, T c) { G[x].eb(y, c), G[y].eb(x, c); }
#define TEST \
INT(testcases); \
while(testcases--)
i128 abs(const i128 &x) { return x > 0 ? x : -x; }
istream &operator>>(istream &is, i128 &v) {
string s;
is >> s;
v = 0;
for(int i = 0; i < (int)s.size(); i++) {
if(isdigit(s[i])) { v = v * 10 + s[i] - '0'; }
}
if(s[0] == '-') { v *= -1; }
return is;
}
ostream &operator<<(ostream &os, const i128 &v) {
if(v == 0) { return (os << "0"); }
i128 num = v;
if(v < 0) {
os << '-';
num = -num;
}
string s;
for(; num > 0; num /= 10) { s.push_back((char)(num % 10) + '0'); }
reverse(s.begin(), s.end());
return (os << s);
}
namespace aux {
template <typename T, unsigned N, unsigned L> struct tp {
static void output(std::ostream &os, const T &v) {
os << std::get<N>(v) << (&os == &cerr ? ", " : " ");
tp<T, N + 1, L>::output(os, v);
}
};
template <typename T, unsigned N> struct tp<T, N, N> {
static void output(std::ostream &os, const T &v) { os << std::get<N>(v); }
};
} // namespace aux
template <typename... Ts> std::ostream &operator<<(std::ostream &os, const std::tuple<Ts...> &t) {
if(&os == &cerr) { os << '('; }
aux::tp<std::tuple<Ts...>, 0, sizeof...(Ts) - 1>::output(os, t);
if(&os == &cerr) { os << ')'; }
return os;
}
template <typename T, typename S, typename U> std::ostream &operator<<(std::ostream &os, const priority_queue<T, S, U> &_pq) {
auto pq = _pq;
vector<T> res;
while(!empty(pq)) res.emplace_back(pq.top()), pq.pop();
return os << res;
}
template <class T, class S> ostream &operator<<(ostream &os, const pair<T, S> &p) {
if(&os == &cerr) { return os << "(" << p.first << ", " << p.second << ")"; }
return os << p.first << " " << p.second;
}
template <class Ch, class Tr, class Container> std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os, const Container &x) {
bool f = true;
if(&os == &cerr) os << "[";
for(auto &y : x) {
if(&os == &cerr)
os << (f ? "" : ", ") << y;
else
os << (f ? "" : " ") << y;
f = false;
}
if(&os == &cerr) os << "]";
return os;
}
#define dump(...) static_cast<void>(0)
#define dbg(...) static_cast<void>(0)
void OUT() { cout << endl; }
template <class Head, class... Tail> void OUT(const Head &head, const Tail &...tail) {
cout << head;
if(sizeof...(tail)) cout << ' ';
OUT(tail...);
}
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
template <class T, class S> constexpr pair<T, S> inf<pair<T, S>> = {inf<T>, inf<S>};
template <class T> void OUT2(const T &t, T INF = inf<T>, T res = -1) { OUT(t != INF ? t : res); }
template <class T> void OUT2(vector<T> &v, T INF = inf<T>, T res = -1) {
fore(e, v) if(e == INF) e = res;
OUT(v);
fore(e, v) if(e == res) e = INF;
}
template <class F> struct REC {
F f;
REC(F &&f_) : f(forward<F>(f_)) {}
template <class... Args> auto operator()(Args &&...args) const { return f(*this, forward<Args>(args)...); }
};
template <class S> vector<pair<S, int>> runLength(const vector<S> &v) {
vector<pair<S, int>> res;
for(auto &e : v) {
if(res.empty() or res.back().fi != e)
res.eb(e, 1);
else
res.back().se++;
}
return res;
}
vector<pair<char, int>> runLength(const string &v) {
vector<pair<char, int>> res;
for(auto &e : v) {
if(res.empty() or res.back().fi != e)
res.eb(e, 1);
else
res.back().se++;
}
return res;
}
struct string_converter {
char start = 0;
char type(const char &c) const { return (islower(c) ? 'a' : isupper(c) ? 'A' : isdigit(c) ? '0' : 0); }
int convert(const char &c) {
if(!start) start = type(c);
return c - start;
}
int convert(const char &c, const string &chars) { return chars.find(c); }
template <typename T> auto convert(const T &v) {
vector<decltype(convert(v[0]))> ret;
ret.reserve(size(v));
for(auto &&e : v) ret.emplace_back(convert(e));
return ret;
}
template <typename T> auto convert(const T &v, const string &chars) {
vector<decltype(convert(v[0], chars))> ret;
ret.reserve(size(v));
for(auto &&e : v) ret.emplace_back(convert(e, chars));
return ret;
}
int operator()(const char &v, char s = 0) {
start = s;
return convert(v);
}
int operator()(const char &v, const string &chars) { return convert(v, chars); }
template <typename T> auto operator()(const T &v, char s = 0) {
start = s;
return convert(v);
}
template <typename T> auto operator()(const T &v, const string &chars) { return convert(v, chars); }
} toint;
template <class T, class F> T bin_search(T ok, T ng, const F &f) {
while((ok > ng ? ok - ng : ng - ok) > 1) {
T mid = ok + ng >> 1;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
template <class T, class F> T bin_search_double(T ok, T ng, const F &f, int iter = 80) {
while(iter--) {
// T mid = (ok + ng) / 2;
T mid = sqrtl(ok * ng);
(f(mid) ? ok : ng) = mid;
}
return ok;
}
struct Setup_io {
Setup_io() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(11);
}
} setup_io;
#endif
#pragma endregion
namespace modular {
constexpr int MOD = 998244353;
const int MAXN = 11000000;
template <int Modulus> class modint;
using mint = modint<MOD>;
using vmint = vector<mint>;
vector<mint> Inv;
mint inv(int x);
template <int Modulus> class modint {
public:
static constexpr int mod() { return Modulus; }
int a;
constexpr modint(const ll x = 0) noexcept : a(((x % Modulus) + Modulus) % Modulus) {}
constexpr int &val() noexcept { return a; }
constexpr const int &val() const noexcept { return a; }
constexpr modint operator-() const noexcept { return modint() - *this; }
constexpr modint operator+() const noexcept { return *this; }
constexpr modint &operator++() noexcept {
if(++a == MOD) a = 0;
return *this;
}
constexpr modint &operator--() noexcept {
if(!a) a = MOD;
a--;
return *this;
}
constexpr modint operator++(int) {
modint res = *this;
++*this;
return res;
}
constexpr modint operator--(int) {
mint res = *this;
--*this;
return res;
}
constexpr modint &operator+=(const modint rhs) noexcept {
a += rhs.a;
if(a >= Modulus) { a -= Modulus; }
return *this;
}
constexpr modint &operator-=(const modint rhs) noexcept {
if(a < rhs.a) { a += Modulus; }
a -= rhs.a;
return *this;
}
constexpr modint &operator*=(const modint rhs) noexcept {
a = (long long)a * rhs.a % Modulus;
return *this;
}
constexpr modint &operator/=(const modint rhs) noexcept {
a = (long long)a * (modular::inv(rhs.a)).a % Modulus;
return *this;
}
constexpr modint pow(long long n) const noexcept {
if(n < 0) {
n %= Modulus - 1;
n = (Modulus - 1) + n;
}
modint x = *this, r = 1;
while(n) {
if(n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
constexpr modint inv() const noexcept { return pow(Modulus - 2); }
constexpr friend modint operator+(const modint &lhs, const modint &rhs) { return modint(lhs) += modint(rhs); }
constexpr friend modint operator-(const modint &lhs, const modint &rhs) { return modint(lhs) -= modint(rhs); }
constexpr friend modint operator*(const modint &lhs, const modint &rhs) { return modint(lhs) *= modint(rhs); }
constexpr friend modint operator/(const modint &lhs, const modint &rhs) { return modint(lhs) /= modint(rhs); }
constexpr friend bool operator==(const modint &lhs, const modint &rhs) { return lhs.a == rhs.a; }
constexpr friend bool operator!=(const modint &lhs, const modint &rhs) { return lhs.a != rhs.a; }
// constexpr friend modint operator^=(const modint &lhs, const modint &rhs) { return modint(lhs) ^= modint(rhs); }
};
vmint Fact{1, 1}, Ifact{1, 1};
mint inv(int n) {
if(n > MAXN) return (mint(n)).pow(MOD - 2);
if(Inv.empty()) Inv.emplace_back(0), Inv.emplace_back(1);
if(Inv.size() > n)
return Inv[n];
else {
for(int i = Inv.size(); i <= n; ++i) {
auto [y, x] = div(int(MOD), i);
Inv.emplace_back(Inv[x] * (-y));
}
return Inv[n];
}
}
mint fact(int n) {
if(Fact.size() > n)
return Fact[n];
else
for(int i = Fact.size(); i <= n; ++i) Fact.emplace_back(Fact[i - 1] * i);
return Fact[n];
}
mint ifact(int n) {
if(Ifact.size() > n)
return Ifact[n];
else
for(int i = Ifact.size(); i <= n; ++i) Ifact.emplace_back(Ifact[i - 1] * inv(i));
return Ifact[n];
}
mint modpow(ll a, ll n) { return mint(a).pow(n); }
mint inv(mint a) { return inv(a.a); }
mint ifact(mint a) { return ifact(a.a); }
mint fact(mint a) { return fact(a.a); }
mint modpow(mint a, ll n) { return modpow(a.a, n); }
mint C(int a, int b) {
if(a < 0 || b < 0) return 0;
if(a < b) return 0;
if(a > MAXN) {
b = min(b, a - b);
mint res = 1;
rep(i, b) res *= a - i, res /= i + 1;
return res;
}
return fact(a) * ifact(b) * ifact(a - b);
}
mint P(int a, int b) {
if(a < 0 || b < 0) return 0;
if(a < b) return 0;
if(a > MAXN) {
mint res = 1;
rep(i, b) res *= a - i;
return res;
}
return fact(a) * ifact(a - b);
}
ostream &operator<<(ostream &os, mint a) {
os << a.a;
return os;
}
istream &operator>>(istream &is, mint &a) {
ll x;
is >> x;
a = x;
return is;
}
ostream &operator<<(ostream &os, const vmint &a) {
if(!a.empty()) {
os << a[0];
for(int i = 1; i < si(a); i++) os << " " << a[i];
}
return os;
}
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace convolution {
namespace internal {
int ceil_pow2(int n) {
int x = 0;
while((1U << x) < (unsigned int)(n)) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if(x < 0) x += m;
return x;
}
struct barrett {
unsigned int _m;
unsigned long long im;
barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
unsigned int umod() const { return _m; }
unsigned int mul(unsigned int a, unsigned int b) const {
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x = (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned int v = (unsigned int)(z - x * _m);
if(_m <= v) v += _m;
return v;
}
};
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if(m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while(n) {
if(n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
constexpr bool is_prime_constexpr(int n) {
if(n <= 1) return false;
if(n == 2 || n == 7 || n == 61) return true;
if(n % 2 == 0) return false;
long long d = n - 1;
while(d % 2 == 0) d /= 2;
for(long long a : {2, 7, 61}) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while(t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if(y != n - 1 && t % 2 == 0) { return false; }
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if(a == 0) return {b, 0};
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while(t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if(m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
if(m == 2) return 1;
if(m == 167772161) return 3;
if(m == 469762049) return 3;
if(m == 754974721) return 11;
if(m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while(x % 2 == 0) x /= 2;
for(int i = 3; (long long)(i)*i <= x; i += 2) {
if(x % i == 0) {
divs[cnt++] = i;
while(x % i == 0) { x /= i; }
}
}
if(x > 1) { divs[cnt++] = x; }
for(int g = 2;; g++) {
bool ok = true;
for(int i = 0; i < cnt; i++) {
if(pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if(ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
void butterfly(std::vector<mint> &a) {
static constexpr int g = internal::primitive_root<mint::mod()>;
int n = int(a.size());
int h = internal::ceil_pow2(n);
static bool first = true;
static mint sum_e[30]; // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i]
if(first) {
first = false;
mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1
int cnt2 = bsf(mint::mod() - 1);
mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
for(int i = cnt2; i >= 2; i--) {
// e^(2^i) == 1
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
mint now = 1;
for(int i = 0; i < cnt2 - 2; i++) {
sum_e[i] = es[i] * now;
now *= ies[i];
}
}
for(int ph = 1; ph <= h; ph++) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
mint now = 1;
for(int s = 0; s < w; s++) {
int offset = s << (h - ph + 1);
for(int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * now;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
now *= sum_e[bsf(~(unsigned int)(s))];
}
}
}
void butterfly_inv(std::vector<mint> &a) {
static constexpr int g = internal::primitive_root<mint::mod()>;
int n = int(a.size());
int h = internal::ceil_pow2(n);
static bool first = true;
static mint sum_ie[30]; // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i]
if(first) {
first = false;
mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1
int cnt2 = bsf(mint::mod() - 1);
mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
for(int i = cnt2; i >= 2; i--) {
// e^(2^i) == 1
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
mint now = 1;
for(int i = 0; i < cnt2 - 2; i++) {
sum_ie[i] = ies[i] * now;
now *= es[i];
}
}
for(int ph = h; ph >= 1; ph--) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
mint inow = 1;
for(int s = 0; s < w; s++) {
int offset = s << (h - ph + 1);
for(int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] = (unsigned long long)(mint::mod() + l.val() - r.val()) * inow.val();
}
inow *= sum_ie[bsf(~(unsigned int)(s))];
}
}
mint z = mint(n).inv();
for(int i = 0; i < n; i++) a[i] *= z;
}
} // namespace internal
std::vector<mint> convolution(std::vector<mint> a, std::vector<mint> b) {
int n = int(a.size()), m = int(b.size());
if(!n || !m) return {};
if(std::min(n, m) <= 60) {
if(n < m) {
std::swap(n, m);
std::swap(a, b);
}
std::vector<mint> ans(n + m - 1);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) { ans[i + j] += a[i] * b[j]; }
}
return ans;
}
int z = 1 << internal::ceil_pow2(n + m - 1);
a.resize(z);
internal::butterfly(a);
b.resize(z);
internal::butterfly(b);
for(int i = 0; i < z; i++) { a[i] *= b[i]; }
internal::butterfly_inv(a);
a.resize(n + m - 1);
// mint iz = mint(z).inv();
// for(int i = 0; i < n + m - 1; i++) a[i] *= iz;
return a;
}
} // namespace convolution
using Poly = vmint;
Poly low(const Poly &f, int s) { return Poly(f.begin(), f.begin() + min<int>(max(s, 1), f.size())); }
Poly operator-(Poly f) {
for(auto &&e : f) e = -e;
return f;
}
Poly &operator+=(Poly &l, const Poly &r) {
l.resize(max(l.size(), r.size()));
rep(i, r.size()) l[i] += r[i];
return l;
}
Poly operator+(Poly l, const Poly &r) { return l += r; }
Poly &operator-=(Poly &l, const Poly &r) {
l.resize(max(l.size(), r.size()));
rep(i, r.size()) l[i] -= r[i];
return l;
}
Poly operator-(Poly l, const Poly &r) { return l -= r; }
Poly &operator<<=(Poly &f, size_t n) { return f.insert(f.begin(), n, 0), f; }
Poly operator<<(Poly f, size_t n) { return f <<= n; }
Poly &operator>>=(Poly &f, size_t n) { return f.erase(f.begin(), f.begin() + min(f.size(), n)), f; }
Poly operator>>(Poly f, size_t n) { return f >>= n; }
Poly operator*(const Poly &l, const Poly &r) { return convolution::convolution(l, r); }
Poly &operator*=(Poly &l, const Poly &r) { return l = l * r; }
Poly &operator*=(Poly &l, const mint &x) {
for(auto &e : l) e *= x;
return l;
}
Poly operator*(const Poly &l, const mint &x) {
auto res = l;
return res *= x;
}
Poly inv(const Poly &f, int s = -1) {
if(s == -1) s = f.size();
Poly r(s);
r[0] = mint(1) / f[0];
for(int n = 1; n < s; n *= 2) {
auto F = low(f, 2 * n);
F.resize(2 * n);
convolution::internal::butterfly(F);
auto g = low(r, 2 * n);
g.resize(2 * n);
convolution::internal::butterfly(g);
rep(i, 2 * n) F[i] *= g[i];
convolution::internal::butterfly_inv(F);
rep(i, n) F[i] = 0;
convolution::internal::butterfly(F);
rep(i, 2 * n) F[i] *= g[i];
convolution::internal::butterfly_inv(F);
rep(i, n, min(2 * n, s)) r[i] -= F[i];
}
return r;
}
Poly integ(const Poly &f) {
Poly res(f.size() + 1);
for(int i = 1; i < (int)res.size(); ++i) res[i] = f[i - 1] / i;
return res;
}
Poly deriv(const Poly &f) {
if(f.size() == 0) return Poly();
Poly res(f.size() - 1);
rep(i, res.size()) res[i] = f[i + 1] * (i + 1);
return res;
}
Poly log(Poly f, int deg = -1) {
if(deg != -1) f.resize(deg + 1);
Poly g = integ(inv(f) * deriv(f));
return Poly{g.begin(), g.begin() + f.size()};
}
Poly exp(Poly f, int deg = -1) {
if(deg != -1) f.resize(deg + 1);
Poly g{1};
while(g.size() < f.size()) {
Poly x(f.begin(), f.begin() + min(f.size(), g.size() * 2));
x[0] += 1;
g.resize(2 * g.size());
x -= log(g);
x *= {g.begin(), g.begin() + g.size() / 2};
rep(i, g.size() / 2, min<int>(x.size(), g.size())) g[i] = x[i];
}
return {g.begin(), g.begin() + f.size()};
}
Poly pow(const Poly &f, ll k, int need = -1) {
const int n = (int)f.size();
if(need == -1) need = n;
int z = 0;
rep(i, n) {
if(f[i].a) break;
z++;
}
if(z * k >= need) return Poly(need);
mint rev = f[z].inv();
Poly res = exp(log((f >> z) * rev, need - k * z) * k) * f[z].pow(k);
res.resize(need - z * k);
res <<= z * k;
return res;
}
struct Prd {
deque<Poly> deq;
Prd() = default;
void emplace(const Poly &f) { deq.emplace_back(f); }
Poly calc() {
if(deq.empty()) return {1};
sort(all(deq), [&](const Poly &f, const Poly &g) { return si(f) < si(g); });
while(deq.size() > 1) {
deq.emplace_back(deq[0] * deq[1]);
for(int i = 0; i < 2; ++i) deq.pop_front();
}
return deq.front();
}
};
Poly prd(vector<Poly> &v) {
Prd p;
for(auto &e : v) p.emplace(e);
return p.calc();
}
vmint power_table(mint x, int len) {
vmint res(len + 1);
res[0] = 1;
rep(i, len) res[i + 1] = res[i] * x;
return res;
}
// calc f(x + a)
Poly TaylorShift(Poly f, mint a) {
int n = f.size();
rep(i, n) f[i] *= fact(i);
reverse(all(f));
Poly g(n, 1);
rep(i, 1, n) g[i] = g[i - 1] * a * inv(i);
f = (f * g);
f.resize(n);
reverse(begin(f), end(f));
rep(i, n) f[i] *= ifact(i);
return f;
}
// ボールの数、一個以上必要な数、入っていなくてもいい数(区別あり)
mint choose(int num, int a, int b = 0) {
if(num == 0) return !a;
return C(num + b - 1, a + b - 1);
}
} // namespace modular
using namespace modular;
// {rank, det(非正方行列の場合は未定義)} を返す
// 型が double や Rational でも動くはず?(未検証)
//
// pivot 候補 : [0, pivot_end)
template <typename T> std::pair<int, T> GaussElimination(vector<vector<T>> &a, int pivot_end = -1, bool diagonalize = false) {
int H = a.size(), W = a[0].size(), rank = 0;
if(pivot_end == -1) pivot_end = W;
T det = 1;
for(int j = 0; j < pivot_end; j++) {
int idx = -1;
for(int i = rank; i < H; i++) {
if(a[i][j] != T(0)) {
idx = i;
break;
}
}
if(idx == -1) {
det = 0;
continue;
}
if(rank != idx) det = -det, swap(a[rank], a[idx]);
det *= a[rank][j];
if(diagonalize && a[rank][j] != T(1)) {
T coeff = T(1) / a[rank][j];
for(int k = j; k < W; k++) a[rank][k] *= coeff;
}
int is = diagonalize ? 0 : rank + 1;
for(int i = is; i < H; i++) {
if(i == rank) continue;
if(a[i][j] != T(0)) {
T coeff = a[i][j] / a[rank][j];
for(int k = j; k < W; k++) a[i][k] -= a[rank][k] * coeff;
}
}
rank++;
}
return make_pair(rank, det);
}
// 解が存在する場合は, 解が v + C_1 w_1 + ... + C_k w_k と表せるとして
// (v, w_1, ..., w_k) を返す
// 解が存在しない場合は空のベクトルを返す
//
// double や Rational でも動くはず?(未検証)
template <typename T> vector<vector<T>> LinearEquation(vector<vector<T>> a, vector<T> b) {
int H = a.size(), W = a[0].size();
for(int i = 0; i < H; i++) a[i].push_back(b[i]);
auto p = GaussElimination(a, W, true);
int rank = p.first;
for(int i = rank; i < H; ++i) {
if(a[i][W] != 0) return vector<vector<T>>{};
}
vector<vector<T>> res(1, vector<T>(W));
vector<int> pivot(W, -1);
for(int i = 0, j = 0; i < rank; ++i) {
while(a[i][j] == 0) ++j;
res[0][j] = a[i][W], pivot[j] = i;
}
for(int j = 0; j < W; ++j) {
if(pivot[j] == -1) {
vector<T> x(W);
x[j] = 1;
for(int k = 0; k < j; ++k) {
if(pivot[k] != -1) x[k] = -a[pivot[k]][j];
}
res.push_back(x);
}
}
return res;
}
int main() {
TEST {
INT(n, m);
vv(mint, a, n, n);
vmint b(n);
b[0] = -1;
b[n - 1] = 1;
vl l, r, w;
rep(m) {
LL(u, v, c);
--u, --v;
mint k = mint(c * 4).inv();
a[u][u] += 2 * k;
a[u][v] -= 2 * k;
a[v][v] += 2 * k;
a[v][u] -= 2 * k;
l.eb(u), r.eb(v), w.eb(c);
}
auto le = LinearEquation(a, b);
dump(le);
auto res = le[0];
mint ans;
rep(i, m) { ans += (res[l[i]] - res[r[i]]).pow(2) * mint(4 * w[i]).inv(); }
ans += res[0] - res[n - 1];
OUT(-ans);
}
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3684kb
input:
4 4 4 1 2 1 2 4 1 1 3 1 3 4 1 3 3 1 2 1 1 3 1 2 3 1 5 6 1 2 1 2 3 3 2 4 1 3 4 1 3 5 1 1 5 8 4 5 1 2 1 1 3 2 2 3 1 3 4 1 4 2 8
output:
1 665496236 713031683 614304219
result:
ok 4 number(s): "1 665496236 713031683 614304219"
Test #2:
score: 0
Accepted
time: 44ms
memory: 38132kb
input:
18 3 3 3 1 716147853 2 1 865756093 3 2 749398397 9 15 7 1 928709747 9 1 692128293 8 2 960581386 6 7 744136630 4 9 233596968 9 7 190944262 3 5 289260315 3 7 164971041 1 8 664146999 5 6 436111746 4 1 780866816 7 5 366276343 8 9 28381218 9 5 140872991 9 2 196864247 4 5 3 4 839263691 2 4 940408725 1 4 4...
output:
509847883 279046442 799909987 81894899 87396695 252566082 696231300 791580749 310547727 575449008 440135980 246650056 287050173 357985276 653404982 532887171 487274780 308326199
result:
ok 18 numbers
Test #3:
score: 0
Accepted
time: 62ms
memory: 70060kb
input:
6 36 69 6 17 677743067 1 29 531808623 30 11 703155711 8 10 892941582 1 36 801802370 9 25 879654751 28 1 428300004 33 1 815419739 1 24 139768084 1 8 183495282 2 31 740704740 4 1 292930294 5 1 976570439 28 31 972831305 17 1 651730241 16 23 277760726 32 24 838263054 2 1 347147900 1 34 105704066 35 9 14...
output:
397416988 997377855 133875520 584693104 870639501 651730094
result:
ok 6 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 20 37 7 4 666597839 20 4 2552558 4 12 449276833 3 20 313325632 8 2 749321823 15 3 893286112 11 20 829400868 15 17 336351940 2 12 87038787 4 17 578479212 19 5 531402067 6 3 390732594 10 16 263059078 18 4 606610768 4 8 324999764 7 2 306113167 5 3 495317708 2 4 193646587 13 7 727928314 3 1 63294221 1...
output:
471559554 643318887 99288483
result:
ok 3 number(s): "471559554 643318887 99288483"
Test #5:
score: 0
Accepted
time: 50ms
memory: 36824kb
input:
3 44 85 16 34 572202176 17 23 919728884 7 32 954531021 16 44 662189312 36 5 165486898 16 32 458385177 13 4 165584205 32 42 53010006 40 44 325480483 11 19 287479705 13 38 896097920 15 13 924124928 22 43 275801574 41 14 366693803 9 31 255010161 16 11 348312510 5 14 291338688 16 43 108459452 16 35 6113...
output:
119959884 147941019 299430476
result:
ok 3 number(s): "119959884 147941019 299430476"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
1 100 197 90 13 869965029 40 33 652981742 20 100 609262992 71 80 776564418 78 15 776967596 100 19 618060914 55 78 644129048 94 87 468426108 45 68 607793883 67 14 861417065 85 51 430869805 58 35 416332523 87 4 220430293 56 41 330849428 67 100 686428759 100 64 954321115 3 93 578946610 22 30 717718287 ...
output:
57004150
result:
ok 1 number(s): "57004150"
Test #7:
score: 0
Accepted
time: 3ms
memory: 9040kb
input:
1 100 197 37 6 491508043 64 61 562781556 85 31 968770484 59 68 468217417 68 62 226821400 26 87 867770696 82 55 180267402 83 1 229431346 44 48 890030452 6 86 774908191 50 64 422040648 89 40 346311095 60 92 584863740 64 80 948682461 25 30 419688139 33 90 304781320 43 44 173243953 77 83 741598604 47 31...
output:
21965378
result:
ok 1 number(s): "21965378"
Test #8:
score: 0
Accepted
time: 50ms
memory: 37448kb
input:
18 10 12 5 9 570792465 1 2 898865579 2 6 894355206 8 10 749093339 9 4 94162006 10 6 804508173 6 3 584217965 7 9 576534175 2 5 959051874 2 7 187295071 9 8 223847747 7 10 543442879 10 12 10 9 862399016 1 2 578680461 8 5 516318540 5 1 234194770 1 6 611676684 5 2 206180466 2 10 967161527 6 9 829929775 3...
output:
662159250 453040104 660616349 339221786 183955 451798707 281162809 844612772 679136700 622982714 424586845 99577783 639247473 550642349 318119205 965911843 112493916 853364601
result:
ok 18 numbers
Test #9:
score: 0
Accepted
time: 70ms
memory: 36560kb
input:
13 10 20 7 3 738772997 4 3 575075131 5 7 901097125 3 2 471669798 9 3 186055301 7 2 508339266 1 10 408675234 7 8 665171988 1 7 245700156 8 10 979869510 6 9 371289239 3 6 471846745 5 1 116126037 5 2 855021288 3 8 66546052 2 10 56178104 1 2 528627305 5 9 358064333 4 8 257982709 6 5 756675355 10 20 2 7 ...
output:
328043116 491213171 323064915 283790283 336460538 790090687 107940926 749963877 323773806 464455545 518617473 877631661 600492895
result:
ok 13 numbers
Test #10:
score: 0
Accepted
time: 61ms
memory: 37332kb
input:
10 10 30 1 10 954541103 9 8 504585169 9 1 317918097 3 10 239321784 3 4 952757866 5 4 886592126 10 5 69364147 2 5 460266425 4 8 111724289 8 2 744688033 7 10 938180765 9 7 40475938 8 7 768680574 8 3 439846699 7 2 311016346 1 8 278968788 9 2 359849550 6 8 233578116 6 9 541658248 2 1 597450261 8 5 95949...
output:
357961433 702966544 152302016 62040242 644817881 40913243 968709886 175468116 736318551 132407483
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
9 20 22 1 16 824474710 7 16 550520209 15 6 995550241 13 15 517346077 15 2 919226212 19 12 791811484 20 3 590268091 1 18 532349751 2 17 404102752 16 9 886911808 15 20 252025389 14 15 988033622 3 7 621443031 1 11 957030493 5 15 647308078 2 1 38956184 12 8 984137454 17 4 149049518 16 12 374901884 4 14 ...
output:
264543472 572625000 639445024 685639935 627774398 681319058 227526591 997109116 359929582
result:
ok 9 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
6 20 40 12 19 298157271 14 16 584748592 4 19 439406024 19 14 564830674 10 19 803900002 15 14 194770878 8 3 226233500 1 18 70454754 13 17 171956539 5 14 380173012 17 12 713769239 12 16 962108568 13 18 279436480 14 10 722802753 8 6 782943207 20 5 444115418 6 4 812025910 8 1 839285091 12 10 653379251 2...
output:
158018450 226883551 418818965 44341117 361169053 194573258
result:
ok 6 numbers
Test #13:
score: 0
Accepted
time: 66ms
memory: 37216kb
input:
5 20 60 16 11 761868756 18 2 733133030 2 13 521351452 1 7 531228541 10 3 669762954 12 6 369997182 19 3 210587670 11 7 281293233 16 19 578268733 18 7 760860287 8 20 283521202 19 6 784662326 18 6 154369347 14 10 169789169 13 6 678431595 15 4 18536326 20 10 382418851 12 5 258295054 20 1 538484393 3 16 ...
output:
191138534 670435538 263226596 786202957 204824602
result:
ok 5 number(s): "191138534 670435538 263226596 786202957 204824602"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
3 50 55 46 19 607379272 18 37 716950001 33 39 30680934 8 1 409907997 18 12 761230520 27 5 418578518 13 27 336286143 5 7 431245480 5 31 823304156 14 22 441986554 4 22 182280095 44 14 284237791 45 27 14314357 11 13 288373411 2 21 950087109 36 10 976423274 41 23 353058189 1 3 95155371 30 39 54523211 5 ...
output:
828459632 806316993 463861688
result:
ok 3 number(s): "828459632 806316993 463861688"
Test #15:
score: 0
Accepted
time: 47ms
memory: 37200kb
input:
2 50 100 27 34 354866464 23 22 505280833 2 35 925966655 4 43 437238578 38 25 851106590 36 17 990643322 15 46 982336460 20 13 699420981 40 42 196430556 5 25 163194318 13 32 932412941 8 2 508019945 24 5 50776290 50 8 668859347 40 2 60243760 39 45 706511131 17 30 352928163 3 44 46233708 50 49 436273019...
output:
823558514 845292819
result:
ok 2 number(s): "823558514 845292819"
Test #16:
score: 0
Accepted
time: 42ms
memory: 37196kb
input:
2 50 150 40 37 525161142 27 17 893212346 30 12 214853800 26 11 74501635 20 1 586669647 19 15 978797409 28 2 434114453 50 5 144260668 42 20 675408324 34 39 357345393 37 41 487030241 40 17 338509008 40 42 275132121 45 40 858467243 32 19 78422894 47 40 342913178 17 9 288198830 10 36 657592544 17 16 594...
output:
878673113 531127142
result:
ok 2 number(s): "878673113 531127142"
Test #17:
score: 0
Accepted
time: 71ms
memory: 37672kb
input:
1 100 105 34 52 585112221 45 74 501017055 29 75 715426704 7 57 814228901 3 44 582817607 75 57 203568149 97 94 648345035 80 70 265162115 61 94 51340350 15 20 986489319 91 60 749686132 58 83 735427377 26 11 444416665 79 71 719215627 82 97 38661549 77 68 335455827 13 84 574049857 36 1 461865326 25 68 2...
output:
519757768
result:
ok 1 number(s): "519757768"
Test #18:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
1 100 200 54 99 578825245 83 72 439019020 33 7 932584304 1 2 806514699 11 41 457545496 9 27 437639791 45 84 750029521 49 76 882654106 63 82 355310572 98 47 664632770 29 90 924987815 94 90 115327293 98 88 309760543 55 29 569287511 21 26 572373488 10 30 744084086 92 11 448322437 59 84 217804985 59 7 9...
output:
460093911
result:
ok 1 number(s): "460093911"
Test #19:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
1 100 300 77 35 966906250 61 20 7431322 49 27 513957627 66 91 838579979 84 77 712970215 89 66 886824961 100 62 790523839 44 58 648117961 6 53 799479675 88 59 478326130 96 21 174528519 21 83 714896928 61 99 467940716 6 23 671317122 58 8 533519224 5 41 641315964 88 30 157402334 83 76 602238323 45 56 3...
output:
930977868
result:
ok 1 number(s): "930977868"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
2 100 99 89 53 429613347 19 33 392517665 91 65 440181771 34 27 794291170 3 27 490502569 6 22 200609748 27 47 97179242 48 35 394899041 22 64 71855925 90 36 800769131 18 58 473659840 35 94 210147630 88 79 665688851 82 21 224454011 96 2 406038042 51 43 950591485 59 71 486580228 49 88 417616713 69 93 28...
output:
977659540 319562460
result:
ok 2 number(s): "977659540 319562460"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
3 5 5 1 2 1 2 3 998244352 3 5 1 5 4 998244352 4 2 1 2 1 1 2 42 4 5 1 2 7808409 2 4 218561241 4 3 971403948 3 1 725031045 3 2 285801149
output:
1 42 112159705
result:
ok 3 number(s): "1 42 112159705"
Extra Test:
score: 0
Extra Test Passed