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