Submission #1204571


Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int C[7];

vint calc(int f0){
    vint X,Y,Z;
    rep(i,7){
        X.pb(i);Y.pb((i+1)%7+7);Z.pb(C[(i+1)%7]);

        X.pb((i+1)%7);Y.pb(i+7);Z.pb(C[(i+1)%7]);
    }

    vint s(14,LLONG_MAX);
    s[0]=f0;

    rep(i,20){
        rep(j,X.size()){
            if(s[X[j]]!=LLONG_MAX)s[Y[j]]=Z[j]-s[X[j]];
            if(s[Y[j]]!=LLONG_MAX)s[X[j]]=Z[j]-s[Y[j]];
        }
    }

    return s;
}

struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

bool check(int f0){
    vint s=calc(f0);

    UnionFindTree uf(7);
    rep(i,7)if(s[i]>0)uf.unite(i,(i+1)%7);
    rep(i,7)if(s[i+7]>0)uf.unite(i,(i+1)%7);

    rep(i,7)if(C[i]&&!uf.areSame(0,i))return false;
    return true;
}

signed main(){
    rep(i,7)cin>>C[i];
    C[0]--;
    if(C[0]<0){
        cout<<"NO"<<endl;
        return 0;
    }


    vint s=calc(0);

    int l=0,r=1e15;
    rep(i,7)chmax(l,-s[i]);
    rep(i,7)chmin(r,s[i+7]);

    if(l>r){
        cout<<"NO"<<endl;
        return 0;
    }

    bool ok=false;
    for(int i=0;i<2;i++){
        if(l+i<=r){
            ok|=check(l+i);
            ok|=check(r-i);
        }
    }

    cout<<(ok?"YES":"NO")<<endl;
    return 0;
}

Submission Info

Submission Time
Task F - 歩くピアニスト
User latte0119
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2323 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 4
AC × 75
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
All sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 01-47.txt, 01-48.txt, 01-49.txt, 01-50.txt, 01-51.txt, 01-52.txt, 01-53.txt, 01-54.txt, 01-55.txt, 01-56.txt, 01-57.txt, 01-58.txt, 01-59.txt, 01-60.txt, 01-61.txt, 01-62.txt, 01-63.txt, 01-64.txt, 01-65.txt, 01-66.txt, 01-67.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 1 ms 256 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 1 ms 256 KB
01-06.txt AC 1 ms 256 KB
01-07.txt AC 1 ms 256 KB
01-08.txt AC 1 ms 256 KB
01-09.txt AC 1 ms 256 KB
01-10.txt AC 1 ms 256 KB
01-11.txt AC 1 ms 256 KB
01-12.txt AC 1 ms 256 KB
01-13.txt AC 1 ms 256 KB
01-14.txt AC 1 ms 256 KB
01-15.txt AC 1 ms 256 KB
01-16.txt AC 1 ms 256 KB
01-17.txt AC 1 ms 256 KB
01-18.txt AC 1 ms 256 KB
01-19.txt AC 1 ms 256 KB
01-20.txt AC 1 ms 256 KB
01-21.txt AC 1 ms 256 KB
01-22.txt AC 1 ms 256 KB
01-23.txt AC 1 ms 256 KB
01-24.txt AC 1 ms 256 KB
01-25.txt AC 1 ms 256 KB
01-26.txt AC 1 ms 256 KB
01-27.txt AC 1 ms 256 KB
01-28.txt AC 1 ms 256 KB
01-29.txt AC 1 ms 256 KB
01-30.txt AC 1 ms 256 KB
01-31.txt AC 1 ms 256 KB
01-32.txt AC 1 ms 256 KB
01-33.txt AC 1 ms 256 KB
01-34.txt AC 1 ms 256 KB
01-35.txt AC 1 ms 256 KB
01-36.txt AC 1 ms 256 KB
01-37.txt AC 1 ms 256 KB
01-38.txt AC 1 ms 256 KB
01-39.txt AC 1 ms 256 KB
01-40.txt AC 1 ms 256 KB
01-41.txt AC 1 ms 256 KB
01-42.txt AC 1 ms 256 KB
01-43.txt AC 1 ms 256 KB
01-44.txt AC 1 ms 256 KB
01-45.txt AC 1 ms 256 KB
01-46.txt AC 1 ms 256 KB
01-47.txt AC 1 ms 256 KB
01-48.txt AC 1 ms 256 KB
01-49.txt AC 1 ms 256 KB
01-50.txt AC 1 ms 256 KB
01-51.txt AC 1 ms 256 KB
01-52.txt AC 1 ms 256 KB
01-53.txt AC 1 ms 256 KB
01-54.txt AC 1 ms 256 KB
01-55.txt AC 1 ms 256 KB
01-56.txt AC 1 ms 256 KB
01-57.txt AC 1 ms 256 KB
01-58.txt AC 1 ms 256 KB
01-59.txt AC 1 ms 256 KB
01-60.txt AC 1 ms 256 KB
01-61.txt AC 1 ms 256 KB
01-62.txt AC 1 ms 256 KB
01-63.txt AC 1 ms 256 KB
01-64.txt AC 1 ms 256 KB
01-65.txt AC 1 ms 256 KB
01-66.txt AC 1 ms 256 KB
01-67.txt AC 1 ms 256 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB
sample-04.txt AC 1 ms 256 KB