結果

問題 No.186 中華風 (Easy)
ユーザー warabi0906warabi0906
提出日時 2023-01-22 10:06:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 18,888 bytes
コンパイル時間 2,871 ms
コンパイル使用メモリ 208,524 KB
実行使用メモリ 30,424 KB
最終ジャッジ日時 2024-06-24 12:27:49
合計ジャッジ時間 3,972 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
30,356 KB
testcase_01 AC 11 ms
30,372 KB
testcase_02 AC 12 ms
30,280 KB
testcase_03 AC 12 ms
30,280 KB
testcase_04 AC 12 ms
30,196 KB
testcase_05 AC 12 ms
30,192 KB
testcase_06 AC 12 ms
30,424 KB
testcase_07 AC 12 ms
30,272 KB
testcase_08 AC 12 ms
30,204 KB
testcase_09 AC 12 ms
30,356 KB
testcase_10 AC 13 ms
30,180 KB
testcase_11 AC 12 ms
30,212 KB
testcase_12 AC 12 ms
30,216 KB
testcase_13 AC 12 ms
30,272 KB
testcase_14 AC 13 ms
30,320 KB
testcase_15 AC 12 ms
30,280 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 12 ms
30,236 KB
testcase_19 AC 12 ms
30,320 KB
testcase_20 AC 12 ms
30,216 KB
testcase_21 AC 11 ms
30,376 KB
testcase_22 AC 12 ms
30,176 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

/*
 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 INS insert
#define all(vec) vec.begin(),vec.end()
#define in(name) ll name;cin >> name
#define ind(name) long double 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 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 nl 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 out("this point ok");
//

//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++;
		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;
    ll sz_count;
    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);
        sz_count=0LL;
        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;
        sz_count++;
        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;
            ll prev=sz_count;
            dfs2(i,now_group);
            now_group++;
            groupsize.PB(sz_count-prev);
        }
        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);
    }
};
/* BIT: RAQ対応BIT
    初期値は a_1 = a_2 = ... = a_n = 0
    ・add(l,r,x): [l,r) に x を加算する
    ・sum(i): a_1 + a_2 + ... + a_i を計算する
    計算量は全て O(logn)
*/
/* BIT: 区間和の更新や計算を行う構造体
    初期値は a_1 = a_2 = ... = a_n = 0
    ・add(i,x): a_i += x とする
    ・sum(i): a_1 + a_2 + ... + a_i を計算する
    計算量は全て O(logn)
*/
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;
   }
 };

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);
    }
};

//
 
//常備構造体宣言のコーナー
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 long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
 
 
 //点と点の距離を返す
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));
}
//
 
 //コンビネーション計算の初期化
void Cinit(){
    k1[0]=1ll;
    rep(i,1,200000)k1[i]=(ll)(i*k1[i-1])%CMOD;
    rep(i,0,200000)k2[i]=Div(1ll,k1[i],CMOD);
}
 
ll com(ll a,ll b){//aの中からb個選ぶ
    if(a<b and a<0 and b<0)return 0;
    return k1[a]*(k2[b]*k2[a-b]%CMOD)%CMOD;
}

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;
}

ll fall_down(ll n,V<ll> arr){
    ll ans = 0;
   BIT b(n+3);  // これまでの数字がどんな風になってるのかをメモる為のBIT
   for (int i = 0; i < n; i++) {
     ans += i - b.sum(arr[i]); // BITの総和 - 自分より左側 = 自分より右側
     b.add(arr[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;
}

inline long long m_mod(long long a, long long m) {
    return (a % m + m) % m;
}

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;  
}

// 中国剰余定理
// リターン値を (r, m) とすると解は x ≡ r (mod. m)
// 解なしの場合は (0, -1) をリターン
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(m_mod(r, M), M);
}

}
//

//構造体宣言のコーナー
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;
}

struct point{
    ll x,y;
};
bool operator < (point a,point b){
    if(a.x<b.x)return true;
    if(a.x==b.x and a.y<b.y)return true;
    return false;
}

//

//GLOBAL変数のコーナー

//
 
//関数のコーナー

//

int main(){
    /*
    文章を読み落としていませんか?
    制約も隅々まで読んでいますか?
    
    注意
    ・セグ木のupdate関数はl,rの値を渡したときにl以上r未満の区間だからご注意を
     rは含みません
    ・BITって1-indexedなんだぜ
     イケてるよな
    ・using namespace Warabi??
    */
    
    //using namespace Warabi;
    
    in(X1);in(Y1);in(X2);in(Y2);in(X3);in(Y3);
    if(X1==0LL and X2==0LL and X3==0LL){
        out(0LL);return 0;
    }
    P<ll,ll> p=Warabi::ChineseRem({X1,X2,X3},{Y1,Y2,Y3});
    if(p.FI==0)out(-1);
    else out(p.FI);
    
}





0