結果
問題 | No.915 Plus Or Multiple Operation |
ユーザー | warabi0906 |
提出日時 | 2023-05-09 19:32:27 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 21,569 bytes |
コンパイル時間 | 3,290 ms |
コンパイル使用メモリ | 218,476 KB |
実行使用メモリ | 30,336 KB |
最終ジャッジ日時 | 2024-11-26 05:03:53 |
合計ジャッジ時間 | 4,252 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 13 ms
30,192 KB |
testcase_01 | AC | 14 ms
30,308 KB |
testcase_02 | AC | 12 ms
30,212 KB |
testcase_03 | AC | 14 ms
30,336 KB |
testcase_04 | AC | 13 ms
30,196 KB |
testcase_05 | AC | 13 ms
30,208 KB |
testcase_06 | AC | 13 ms
30,216 KB |
testcase_07 | AC | 12 ms
30,208 KB |
testcase_08 | AC | 12 ms
30,300 KB |
testcase_09 | AC | 13 ms
30,208 KB |
testcase_10 | AC | 13 ms
30,208 KB |
testcase_11 | AC | 13 ms
30,236 KB |
testcase_12 | AC | 13 ms
30,268 KB |
ソースコード
/* Hi,I am warabi. Welcome to my coding space. Let me give you a great word of advice. "The pen is mightier than the sword" -by Edward Bulwer-Lytton _,,....,,_ _人人人人人人人人人人人人人人人人人人_ -''":::::::::::::`''> ゆっくりできるとでも? < ヽ::::::::::::::::::::: ̄^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y ̄ |::::::;ノ´ ̄\:::::::::::\_,. -‐ァ __ _____ ______ |::::ノ ヽ、ヽr-r'"´ (.__ ,´ _,, '-´ ̄ ̄`-ゝ 、_ イ、 _,.!イ_ _,.ヘーァ'二ハ二ヽ、へ,_7 'r ´ ヽ、ン、 ::::::rー''7コ-‐'"´ ; ', `ヽ/`7 ,'==─- -─==', i r-'ァ'"´/ /! ハ ハ ! iヾ_ノ i イ iゝ、イ人レ/_ルヽイ i | !イ´ ,' | /__,.!/ V 、!__ハ ,' ,ゝ レリイi (ヒ_] ヒ_ン ).| .|、i .|| `! !/レi' (ヒ_] ヒ_ン レ'i ノ !Y!"" ,___, "" 「 !ノ i | ,' ノ !'" ,___, "' i .レ' L.',. ヽ _ン L」 ノ| .| ( ,ハ ヽ _ン 人! | ||ヽ、 ,イ| ||イ| / ,.ヘ,)、 )>,、 _____, ,.イ ハ レ ル` ー--─ ´ルレ レ´ Take your time. GIVE ME AC!!!!!!!!!!!!!!!!!!!!!!!!! */ #include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define V vector #define rep(i,a,b) for(ll i=a;i<b;i++) #define brep(i,a,b) for(ll i=a;i>=b;i--) #define reph(i,vec) for(auto &i:vec) #define FI first #define SE second #define P pair #define PB push_back #define EB emplace_back #define INS insert #define all(vec) vec.begin(),vec.end() #define in(name) ll name;cin >> name #define ins(name) string name;cin >> name; #define inc(name) char name;cin >> name #define ing(name,size,E) vector<vector<ll>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);name[b].PB(a);} #define ing_on(name,size,E) vector<vector<long long>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);} #define ing_cost(name,size,E) vector<vector<P<ll,ll>>> name(size);rep(i,0,E){in(a);in(b);in(c);a--;b--;name[a].PB({b,c});name[b].PB({a,c});} #define invll(name,size) vector<ll> name(size);reph(i,name)cin >> i #define invvll(name,size1,size2) vector<vector<long long>> name(size1,vector<long long>(size2));reph(v,name)reph(i,v)cin>>i; #define invp(name,size) vector<P<ll,ll>> name(size);for(ll i=0;i<size;i++)cin >> name[i].FI >> name[i].SE #define out(n) cout << (n) << endl #define _out(n) cout << " " << (n) << endl; #define notout(n) cout << (n) #define out_(n) cout << (n) << " " #define set_out(n,k) cout << fixed << setprecision(k) << (n) << endl; #define set_notout(n,k) cout << fixed << setprecision(k) << (n) << endl; #define set_out_(n,k) cout << fixed << setprecision(k) << (n) << " "; #define vout(vec) for(int i=0;i<vec.size();i++)cout<<(i?" ":"")<<(vec[i]);cout<<endl; #define nel cout<<endl; #define getbit(n,k) (((1LL<<(k))&(n))>0) #define INF 1000000000000000000 #define MOD 1000000007 #define MOD2 998244353 #define CMOD MOD2 #define EPS 0.00000001 //debug #define bug assert(false); #define debug cout<<"OK Line "<<__LINE__<<endl; // //constexpr long double PI=3.14159265358979323846; //template template<typename T> inline bool chmax(T &a,const T b){if(a<b){a=b;return true;}return false;} template<typename T> inline bool chmin(T &a,const T b){if(a>b){a=b;return true;}return false;} // namespace Warabi{ //常備変数のコーナー V<bool> primes(3001000,true); V<ll> prime_list; V<ll> prime_rui(3001000,0LL); V<bool> visiteded(300100); V<bool> afed(300100,false); V<ll> k1(200100,0ll); V<ll> k2(200100,0ll); // //常備構造体宣言のコーナー class UnionFind { private: ll NumberOfElements; ll Not1NumberOfelements; public: vector<ll> par; vector<ll> SIZE; void init(ll sz) { par.resize(sz, -1LL); SIZE.resize(sz,1LL); NumberOfElements=sz; Not1NumberOfelements=0ll; } ll root(ll pos) { if (par[pos] == -1) return pos; par[pos] = root(par[pos]); return par[pos]; } bool same(ll u, ll v) { if (root(u) == root(v)) return true; return false; } ll SZ(ll u){ return SIZE[root(u)]; } ll noe(){ return NumberOfElements; } ll nnoe(){ return Not1NumberOfelements; } bool unite(ll u, ll v) { u = root(u); v = root(v); if (u == v){ return false; } if(SZ(u) == 1LL and SZ(v) == 1LL)Not1NumberOfelements++; if(u<v)swap(u,v); par[u] = v; SIZE[v] += SIZE[u]; NumberOfElements--; return true; } }; class SCC{ public: V<V<ll>> G; V<V<ll>> UG; V<ll> order; V<ll> GROUP; V<bool> visited; V<ll> groupsize; void init(ll sz){ G.resize(sz,V<ll>(0)); UG.resize(sz,V<ll>(0)); GROUP.resize(sz,-1ll); visited.resize(sz,false); return; } void dfs(ll now){ visited[now]=true; reph(i,G[now]){ if(visited[i])continue; dfs(i); } order.PB(now); return; } void dfs2(ll now,ll group){ GROUP[now]=group; reph(i,UG[now]){ if(GROUP[i]!=-1ll and GROUP[i]!=group)continue; if(GROUP[i]!=-1ll)continue; dfs2(i,group); } return; } void make_group(V<V<ll>> Graph_function){ G=Graph_function; rep(i,0,(ll)G.size()){ reph(j,G[i]){ UG[j].PB(i); } } rep(i,0,(ll)G.size()){ if(visited[i])continue; dfs(i); } reverse(all(order)); ll now_group=0LL; reph(i,order){ if(GROUP[i]!=-1)continue; dfs2(i,now_group); now_group++; } groupsize.resize(now_group,0ll); rep(i,0,(ll)G.size())groupsize[GROUP[i]]++; return; } }; template<typename X,typename M> class SegmentTree{ public: long long sz; using FX=function<X(X,X)>; using FA=function<X(X,M)>; using FM=function<M(M,M)>; const FX fx; const FA fa; const FM fm; const X ex; const M em; vector<X> node; vector<M> lazy; SegmentTree(long long sz_,FX fx_,FA fa_,FM fm_,X ex_,M em_):sz(),fx(fx_),fa(fa_),fm(fm_),ex(ex_),em(em_){ long long n=1LL; while(n<sz_)n*=2; sz=n; node.resize(sz*2-1,ex); lazy.resize(sz*2-1,em); } void set(long long index,X x){ node[index+sz-1]=x; return; } void build(){ for(int i=sz-2;i>=0;i--)node[i]=fx(node[i*2+1],node[i*2+2]); return; } void eval(long long k){ if(lazy[k]==em)return; if(k<sz-1){ lazy[k*2+1]=fm(lazy[k*2+1],lazy[k]); lazy[k*2+2]=fm(lazy[k*2+2],lazy[k]); } node[k]=fa(node[k],lazy[k]); lazy[k]=em; } void update_sub(long long a,long long b,M x,long long k,long long l,long long r){ //cout << " " << a << " " << b << " " << l << " " << r << endl; eval(k); if(a<=l and r<=b){ lazy[k]=fm(lazy[k],x); //cout<<" "<<lazy[k]<<endl; eval(k); return; } else if(a<r and l<b){ update_sub(a,b,x,k*2+1,l,(l+r)/2); update_sub(a,b,x,k*2+2,(l+r)/2,r); node[k]=fx(node[k*2+1],node[k*2+2]); return; } return; } void update(long long a,long long b,M x){ update_sub(a,b,x,0LL,0LL,sz); return; } void add_sub(long long a,X x,long long k,long long l,long long r){ eval(k); node[k]+=x; if(k<sz-1){ long long mid=(l+r)/2; if(a<mid)add_sub(a,x,k*2+1,l,mid); else add_sub(a,x,k*2+2,mid,r); } return; } void add(long long a,X x){ add_sub(a,x,0LL,0LL,sz); } X query_sub(long long a,long long b,long long k,long long l,long long r){ eval(k); if(r<=a or b<=l)return ex; else if(a<=l and r<=b)return node[k]; else{ X Xl=query_sub(a,b,k*2+1,l,(l+r)/2); X Xr=query_sub(a,b,k*2+2,(l+r)/2,r); //cout<<" / "<<Xl<<" "<<Xr<<endl; return fx(Xl,Xr); } } X query(long long a,long long b){ return query_sub(a,b,0LL,0LL,sz); } inline X operator [] (long long index){ return query(index,index+1); } }; template<typename T> class multimap{ private: map<T,ll> mp; public: void add(ll x){ mp[x]++; return; } void del(ll x){ mp[x]--; if(mp[x]<1)mp.erase(x); return; } T maximum(){ return mp.rbegin()->first; } T minimum(){ return mp.begin()->first; } }; class LCA{ public: vector<vector<long long>> parent; vector<long long> dist; vector<vector<long long>> G; LCA(const vector<vector<long long>> &gr){init(gr);} void dfs(long long v,long long p,long long d){ parent[0][v]=p; dist[v]=d; for(long long next : G[v]){ if(next==p)continue; dfs(next,v,d+1); } return; } void init(const vector<vector<long long>> &gr){ G=gr; parent.assign(33,vector<long long>(G.size(),-1LL)); dist.assign(G.size(),-1LL); dfs(0LL,-1LL,0LL); for(int i=0;i<32;i++){ for(int j=0;j<(int)G.size();j++){ if(parent[i][j]<0LL){ parent[i+1][j]=-1LL; } else{ parent[i+1][j]=parent[i][parent[i][j]]; } } } return; } long long lca(long long u,long long v){ if(dist[u]<dist[v])swap(u,v); long long between=dist[u]-dist[v]; for(int i=0;i<33;i++){ if(between&(1LL<<i)){u=parent[i][u];} } if(u==v)return u; for(int i=32;i>=0;i--){ if(parent[i][u]!=parent[i][v]){ u=parent[i][u]; v=parent[i][v]; } } assert(parent[0][u]==parent[0][v]); return parent[0][u]; } long long get_dist(long long u,long long v){ return dist[u]+dist[v]-2*dist[lca(u,v)]; } bool on_path(long long u,long long v,long long a){ return get_dist(u,v)==get_dist(u,a)+get_dist(v,a); } }; class nCk { public: const long long m; const long long MAXIMUM = 1000000; vector<long long> fac, facinv, inv; nCk(long long m_); ~nCk(); long long com(long long n, long long k)const; }; nCk::nCk(long long m_):m(m_) { fac.resize(MAXIMUM + 3); facinv.resize(MAXIMUM + 3); inv.resize(MAXIMUM + 3); fac[0] = fac[1] = 1; facinv[0] = facinv[1] = 1; inv[1] = 1; for (long long i = 2; i < MAXIMUM + 2; i++) { fac[i] = fac[i - 1] * i % m; inv[i] = m - inv[m % i] * (m / i) % m; facinv[i] = facinv[i - 1] * inv[i] % m; } } nCk::~nCk(){} long long nCk::com(long long n, long long k)const { if(k==0)return 1; if (n < k)return 0LL; assert(!(n < 0 || k < 0)); return fac[n] * (facinv[k] * facinv[n - k] % m) % m; } // //常備構造体宣言のコーナー struct STC{ ll s,t,cost; }; // //常備関数のコーナー void Yes(bool f){cout<<(f?"Yes":"No")<<endl;} void YES(bool f){cout<<(f?"YES":"NO")<<endl;} //木の直径を求める STC Cdiameter(V<V<P<ll,ll>>> G,ll start,bool type){ visiteded=afed; queue<ll> sirabe; sirabe.push(start); V<ll> short_load(G.size(),0LL); while(!sirabe.empty()){ ll s=sirabe.front(); sirabe.pop(); visiteded[s]=true; reph(i,G[s]){ if(visiteded[i.FI])continue; short_load[i.FI]=short_load[s]+i.SE; sirabe.push(i.FI); } } ll far_max=-1LL; ll element=-1LL; rep(i,0,(ll)G.size()){ if(far_max>=short_load[i])continue; far_max=short_load[i]; element=i; } if(type)return Cdiameter(G,element,false); else return {start,element,far_max}; } //素数の取得 void prime_init(){ V<bool> at(3001000,true); primes=at; primes[0]=primes[1]=false; rep(i,2,3000100){ if(!primes[i])continue; for(ll j=i*2;j<=300100;j+=i)primes[j]=false; } rep(i,1,3000100){ if(primes[i]){ prime_list.PB(i); prime_rui[i]=prime_rui[i-1]+1; } else{ prime_rui[i]=prime_rui[i-1]; } } return; } //modpow long long modpow(long long a, long long b, long long m) { long long p = 1, q = a; for (int i = 0; i < 63; i++) { if ((b & (1LL << i)) != 0) { p *= q; p %= m; } q *= q; q %= m; } return p; } //逆元 long long Div(long long a, long long b, long long m) { return (a * modpow(b, m - 2, m)) % m; } //点と点の距離を返す long double Dis(ll ax,ll ay,ll bx,ll by){ return sqrt(pow(ax-bx,2)+pow(ay-by,2)); } //二つのベクトルから平行四辺形の面積を返す ll he(ll x0,ll y0,ll x1,ll y1,ll x2,ll y2){//外積を二で割る return abs((x1-x0)*(y2-y0)-(x2-x0)*(y1-y0)); } // template<typename T> ll Lis_size(V<T> arr,ll sz){ const T TINF=numeric_limits<T>::max(); V<T> DP(sz+1,TINF); DP[0]=-TINF; rep(i,0,sz){ *lower_bound(all(DP),arr[i])=arr[i]; } ll ans=0LL; rep(i,1,sz+1){ if(DP[i]!=TINF)ans=i; } return ans; } string toBinary(ll n){ string r; while (n != 0LL){ r += ( n % 2LL == 0LL ? "0" : "1" ); n /= 2LL; } return r; } template<typename T> V<ll> press(V<T> arr){ V<T> X=arr; sort(all(X)); X.erase(unique(all(X)),X.end()); V<ll> ans(arr.size()); rep(i,0LL,(ll)arr.size()){ ans[i]=lower_bound(all(X),arr[i])-X.begin(); } return ans; } P<V<V<ll>>,V<V<P<ll,ll>>>> warshall_floyd(ll N,V<V<P<ll,ll>>> G){ V<V<ll>> DP(N,V<ll>(N,INF)); rep(i,0,N)DP[i][i]=0LL; V<V<P<ll,ll>>> prev(N,V<P<ll,ll>>(N,{INF,INF})); rep(i,0,N){ reph(j,G[i]){ DP[i][j.FI]=j.SE; prev[i][j.FI]={i,j.FI}; } } rep(k,0,N){ rep(i,0,N){ rep(j,0,N){ if(chmin(DP[i][j],DP[i][k]+DP[k][j])){ prev[i][j]=prev[k][j]; } } } } return {DP,prev}; } template<typename T> void to_sum(V<T> &arr){ rep(i,0,(ll)arr.size()-1LL){ arr[i+1]+=arr[i]; } return; } template<typename T> void including_map(ll H,ll W,V<V<T>> &G,T c){ V<V<T>> new_G(H+2,V<T>(W+2)); rep(i,0,W+2)new_G[0][i]=c; rep(i,1,H+1){ new_G[i][0]=c; new_G[i][W+1]=c; rep(j,1,W+1){ new_G[i][j]=G[i-1][j-1]; } } rep(i,0,W+2)new_G[H+1][i]=c; G=new_G; return; } struct BIT { private: vector<int> bit; int N; public: BIT(int size) { N = size; bit.resize(N + 1); } // 一点更新です void add(int a, int w) { for (int x = a; x <= N; x += x & -x) bit[x] += w; } // 1~Nまでの和を求める。 int sum(int a) { int ret = 0; for (int x = a; x > 0; x -= x & -x) ret += bit[x]; return ret; } }; ll fall_down(ll n,const V<ll> &v){ ll ans = 0; BIT b(n); // これまでの数字がどんな風になってるのかをメモる為のBIT for (int i = 0; i < n; i++) { ans += i - b.sum(v[i]); // BITの総和 - 自分より左側 = 自分より右側 b.add(v[i], 1); // 自分の位置に1を足す } return ans; } set<ll> factor(ll N){ set<ll> ans; for(ll i=1LL;i*i<=N;i++){ if(N%i)continue; ans.INS(i); ans.INS(N/i); } return ans; } V<ll> dijkstra(ll sz,V<V<P<ll,ll>>> G,ll s){ V<ll> ans(sz,INF);ans[s]=0LL; priority_queue<P<ll,ll>,vector<P<ll,ll>>,greater<P<ll,ll>>> examine; examine.push({0LL,s}); while(examine.size()){ P<ll,ll> p=examine.top(); examine.pop(); ll now=p.SE,dist=p.FI; if(ans[now]<dist)continue; reph(i,G[now]){ ll next=i.FI,c=i.SE; if(chmin(ans[next],dist+c)){ examine.push({dist+c,next}); } } } return ans; } set<ll> pass(const V<V<ll>> &G,ll s,ll t){ V<bool> visited(G.size(),false); set<ll> ans,res; function<void(ll)> dfs=[&](ll now){ visited[now]=true; res.INS(now); if(now==t){ ans=res; } reph(next,G[now]){ if(visited[next])continue; dfs(next); } res.erase(now); return; }; dfs(s); return ans; } // 負の数にも対応した mod (a = -11 とかでも OK) inline long long mod(long long a, long long m) { long long res = a % m; if (res < 0) res += m; return res; } // 拡張 Euclid の互除法 long long extGCD(long long a, long long b, long long &p, long long &q) { if (b == 0) { p = 1; q = 0; return a; } long long d = extGCD(b, a%b, q, p); q -= a/b * p; return d; } long long extGcd(long long a, long long b, long long &p, long long &q) { if (b == 0) { p = 1; q = 0; return a; } long long d = extGcd(b, a%b, q, p); q -= a/b * p; return d; } // 逆元計算 (ここでは a と m が互いに素であることが必要) long long modinv(long long a, long long m) { long long x, y; extGCD(a, m, x, y); return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので } // Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない) // for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (mod. m[k])" // coeffs[k] = m[0]m[1]...m[k-1] // constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2] long long Garner(vector<long long> b, vector<long long> m, long long Mmod) { m.push_back(Mmod); // banpei vector<long long> coeffs((int)m.size(), 1); vector<long long> constants((int)m.size(), 0); for (int k = 0; k < (int)b.size(); ++k) { long long t = mod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]); for (int i = k+1; i < (int)m.size(); ++i) { (constants[i] += t * coeffs[i]) %= m[i]; (coeffs[i] *= m[k]) %= m[i]; } } return constants.back(); } pair<long long, long long> ChineseRem(const vector<long long> &b, const vector<long long> &m) { long long r = 0, M = 1; for (int i = 0; i < (int)b.size(); ++i) { long long p, q; long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d) if ((b[i] - r) % d != 0) return make_pair(0, -1); long long tmp = (b[i] - r) / d * p % (m[i]/d); r += M * tmp; M *= m[i]/d; } return make_pair(mod(r, M), M); } map<ll,ll> bunkai(ll n){ map<ll,ll> ans; ll Nn=n; for(int i=2;i*i<=Nn;i++){ while(n%i==0){ n/=i; ans[i]++; } } if(n>1){ans[n]++;} return ans; } template<typename T> void RLE(vector<T> &arr){ vector<T> res; res.push_back(arr[0]); for(const T t:arr){ if(res.back()!=t)res.push_back(t); } arr=res; return; } template<typename T> vector<pair<T,long long>> RLE(vector<T> arr){ vector<pair<T,long long>> res; res.emplase_back(arr[0]); for(const T t:arr){ if(res.back()!=t)res.emplase_back(t,1ll); else res.back().second++; } return res; } vector<pair<long long,long long>> EulerTour(const vector<vector<long long>> &G){ long long N=(long long)G.size(); vector<pair<long long,long long>> res(N); long long now=0ll; function<void(long long,long long)> dfs=[&](long long v,long long p){ res[v].first=now; ++now; for(const long long next:G[v]){ if(next==p)continue; dfs(next,v); } res[v].second=now; ++now; return; }; dfs(0,-1ll); return res; } } namespace Guest{ }; // //構造体宣言のコーナー struct P2{ ll l,r; }; bool operator < (P2 a,P2 b){ if(a.r<b.r)return true; if(a.r==b.r and a.l<b.l)return true; return false; } long long gcd(long long a,long long b){ if(b==0LL)return a; return gcd(b,a%b); } long long lcm(long long a,long long b){ return a*b/gcd(a,b); } long long mpow(long long a,long long b){ long long res=1ll; for(long long i=0;i<b;i++)res*=a; return res; } signed main(){ /* 文章を読み落としていませんか? 制約も隅々まで読んでいますか? 注意 ・セグ木のupdate関数はl,rの値を渡したときにl以上r未満の区間だからご注意を rは含みません ・BITって1-indexedなんだぜ イケてるよな ・転倒数求める関数、0を含んでると使えないらしいぜ ・using namespace Warabi?? */ //using namespace Warabi; in(Q); while(Q--){ in(A);in(B);in(C); if(C==1){ out(-1); continue; } if(A==1){ out(B);continue; } V<ll> TC;ll p=C,cnt=0ll; while(A){ TC.PB(A%p/(p/C)); if(A%p)++cnt; A-=A%p; p*=C; } out((TC.size()-1+cnt-(TC[TC.size()-2]+TC[TC.size()-1]*C<=2*(C-1) and TC[TC.size()-1] and TC[TC.size()-2]?1:0))*B); } }