QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #159265 | #7111. Press the Button | ucup-team1469# | AC ✓ | 8ms | 3868kb | C++17 | 14.1kb | 2023-09-02 17:42:50 | 2023-09-02 17:42:51 |
Judging History
answer
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif
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>>;
#define overload5(a, b, c, d, e, name, ...) name
#define overload4(a, b, c, d, name, ...) name
#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 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 RSORT(v) sort(rall(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 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 LD(...) \
ld __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(ld &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<class T> void prt_(T a){ cout<<a; }
template<class T,class U> void prt_(pair<T,U> a){ cout<<"{"<<a.fi<<", "<<a.se<<"}"; }
void prt_(ld a){ printf("%.15Lf",a); }
template<class T> void prt(vc<T> a){
for(size_t i=0;i<a.size();++i){
prt_(a[i]);
cout<<" \n"[i==a.size()-1];
}
}
template<class T> void prt(vvc<T> a){
for(auto& v:a){
for(size_t i=0;i<v.size();++i){
prt_(v[i]);
cout<<" \n"[i==v.size()-1];
}
}
}
template<class T> void prt(T a){ prt_(a),cout<<"\n"; }
template<class T,class... Args> void prt(T a,Args... args){ prt_(a),cout<<" ",prt(args...); }
template<class Head,class... Tail> struct multi_dim_vector{ using type=vc<typename multi_dim_vector<Tail...>::type>; };
template<class T> struct multi_dim_vector<T>{ using type=T; };
template<class T,class Arg> vc<T> mvec(int n,Arg&& arg){ return vc<T>(n,arg); }
template<class T,class... Args> class multi_dim_vector<Args...,T>::type mvec(int n,Args&&... args){
return typename multi_dim_vector<Args...,T>::type(n,mvec<T>(args...));
}
template<class T> T REVed(T a){
reverse(a.begin(),a.end());
return a;
}
template<class T> T SORTed(T a){
sort(a.begin(),a.end());
return a;
}
template<class T> T RSORTed(T a){
sort(a.rbegin(),a.rend());
return a;
}
vi iota(int n){
vi res(n);
iota(res.begin(),res.end(),0);
return res;
}
template <class T> bool chmax(T &a, T b){ return (a < b ? a = b, 1 : 0); }
template <class T> bool chmin(T &a, T b){ return (a > b ? a = b, 1 : 0); }
template<class T> auto runLength(T a) -> vc<pair<typename decltype(a)::value_type,ll>>{
int n=a.size();
vc<pair<typename decltype(a)::value_type,ll>> res;
if(n==0){ return res; }
typename decltype(a)::value_type now=a[0];
ll l=1;
rep(i,1,n){
if(a[i-1]==a[i]){ l++; }
else{
res.pb(now,l);
now=a[i],l=1;
}
}
res.pb(now,l);
return res;
}
template<int mod> struct mymodint{
ll x;
static constexpr ll get_mod(){ return mod; }
ll val(){ return x; }
mymodint(ll x_=0):x((x_%mod+mod)%mod){}
mymodint operator-(){ return (x==0)?0:mod-x; }
mymodint operator+(mymodint rhs){ return mymodint(*this)+=rhs; }
mymodint operator-(mymodint rhs){ return mymodint(*this)-=rhs; }
mymodint operator*(mymodint rhs){ return mymodint(*this)*=rhs; }
mymodint operator/(mymodint rhs){ return mymodint(*this)/=rhs; }
mymodint pow(ll rhs){
mymodint res=1,now=(*this);
while(rhs){
res*=((rhs&1)?now:1),now*=now,rhs>>=1;
}
return res;
}
mymodint& operator+=(mymodint rhs){
x+=rhs.x,x-=((x>=mod)?mod:0);
return (*this);
}
mymodint& operator-=(mymodint rhs){
x-=rhs.x;
x+=((x<0)?mod:0);
return (*this);
}
mymodint& operator*=(mymodint rhs){
x=x*rhs.x%mod;
return (*this);
}
mymodint& operator/=(mymodint rhs){ return (*this)*=rhs.pow(mod-2); }
bool operator==(mymodint rhs){ return x==rhs.x; }
bool operator!=(mymodint rhs){ return x!=rhs.x; }
};
template<int mod> using modint=
#if __has_include(<atcoder/all>)
atcoder::static_modint<mod>;
#else
mymodint<mod>;
#endif
template<int mod> std::ostream& operator<<(std::ostream& os,modint<mod> x){
return os<<(x.val());
}
template<int mod> std::istream& operator>>(std::istream& is,modint<mod>& x){
ll t;
is>>t,x=t;
return is;
}
template<class T> struct cmb{
vc<T> fac,ifac;
cmb(int mx=3000000):fac(mx+1,1),ifac(mx+1,1){
for(int i=1;i<=mx;++i){ fac[i]=fac[i-1]*i; }
ifac[mx]/=fac[mx];
for(int i=mx;i>0;--i){ ifac[i-1]=ifac[i]*i; }
}
T operator()(ll n,ll k){
if(n<0||k<0||n<k){ return 0; }
return fac[n]*ifac[k]*ifac[n-k];
}
T f(ll n){
return n<0?T(0):fac[n];
}
T fi(ll n){
return n<0?T(0):ifac[n];
}
};
// sum_{0 <= i < N} (ai + b) // m
template <typename T>
T sum_of_floor(T n, T m, T a, T b) {
T ret = 0;
if (a >= m) ret += (n - 1) * n * (a / m) / 2, a %= m;
if (b >= m) ret += n * (b / m), b %= m;
T y = (a * n + b) / m;
if (y == 0) return ret;
T x = y * m - b;
ret += (n - (x + a - 1) / a) * y;
ret += sum_of_floor(y, a, m, (a - x % a) % a);
return ret;
}
int main(){
using fp=modint<998244353>;
INT(cs);
auto f=[&](ll A,ll C,ll T,ll V) -> ll{
__int128_t res=__int128_t(T/A-(T-V)/A)*(T/C);
res+=sum_of_floor<__int128_t>((T-V)/A+1,C,A,V);
res-=sum_of_floor<__int128_t>(T/A+1,C,A,0);
return res;
};
rep(cs){
LL(A,B,C,D,V,T);
ll ans=(B-1)*(T/A+1)+(D-1)*(T/C+1);
V=min(V,T);
if(A>C){ swap(A,C);swap(B,D); }
if(A<=V){
prt(B*(T/A+1)+D*(T/C+1)-1);
continue;
}
ans+=f(A,C,T,V);
ans+=f(C,A,T,V);
ans+=T/(A*C/gcd(A,C))+1;
prt(ans);
}
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3596kb
input:
2 8 2 5 1 2 18 10 2 5 1 2 10
output:
6 4
result:
ok 2 number(s): "6 4"
Test #2:
score: 0
Accepted
time: 8ms
memory: 3560kb
input:
1000 8 6 2 6 3 17 1 6 1 1 1 30 5 4 8 8 1 31 7 6 10 3 6 12 9 1 4 4 3 38 3 3 5 8 1 8 9 1 5 2 3 18 6 10 10 8 2 40 9 6 9 10 3 9 2 5 1 10 10 39 7 7 1 2 4 19 8 10 8 6 7 36 2 9 1 1 7 17 1 2 3 5 6 14 8 8 8 7 1 46 6 9 3 9 4 6 10 8 1 7 10 18 7 1 7 10 3 50 1 10 2 1 5 1 5 8 4 9 7 44 9 2 5 4 7 42 9 1 2 1 1 20 5 ...
output:
71 216 52 16 38 22 7 102 30 499 60 75 98 54 84 44 148 80 20 179 45 4 463 139 56 30 45 127 204 121 42 69 38 98 63 121 25 142 17 75 24 175 114 40 32 11 29 85 35 7 66 49 492 49 49 14 17 53 431 161 94 27 21 135 71 92 33 290 57 300 18 89 155 55 10 219 203 390 28 50 67 213 26 18 27 19 128 101 118 62 46 15...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
100 9 9 3 1 1 2 5 5 7 7 7 50 2 1 8 10 10 45 3 4 5 7 7 38 1 6 9 5 2 13 5 6 7 9 1 29 10 1 4 3 3 19 6 10 10 8 7 3 9 3 10 3 3 14 9 7 1 7 8 38 3 78 5 43 5 958 4 98 3 42 10 7 3 16 9 71 7 52 1 70 3 86 3 410 10 44 1 56 3 628 9 15 9 94 10 15 9 95 9 61 2 525 2 23 8 37 10 108 5 92 3 65 10 331 6 54 6 44 3 537 2...
output:
9 110 82 107 93 73 13 17 10 307 33215 321 713 40551 37995 217 9145 1782 13378 8730 270 2433 143 17 30 136 10 82 33 97 733 126 2917 623 364 1448 1212 872 268 1031 1601 3889 122 523 819 83 17513 277 2973 4651 202187 42602 17225 7881 32574 7087 4453 34029 20529 17520 58488 189327 14380 67133 90956 4328...
result:
ok 100 numbers
Extra Test:
score: 0
Extra Test Passed