Submission #1792973
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define mod 1000000007 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define repn(i,x) for(int i=1;i<=x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) ll c[7]; ll e[7][7]; int main(){ rep(i,7) cin>>c[i]; if(c[0] == 0){ puts("NO"); return 0; } if(c[0] == 1){ int n = c[1]+c[2]+c[3]+c[4]+c[5]+c[6]; puts(n?"NO":"YES"); return 0; } rep(i,7)rep(j,7) e[i][j] = -1e18; e[1][2] = 100000000000000000LL; c[0]--; while(1){ rep(i,7){ if(e[i][(i+1)%7] < -5e17 || e[(i+1)%7][i] < -5e17) goto DO; } break; DO:; rep(i,7){ int a = (6+i)%7; int b = (i+1)%7; if(e[a][i] < -5e17 && e[b][i] < -5e17) continue; if(e[a][i] >= -5e17 && e[b][i] >= -5e17) continue; if(e[a][i] >= -5e17){ e[b][i] = c[i]-e[a][i]; } else{ e[a][i] = c[i]-e[b][i]; } } rep(i,7){ int a = (6+i)%7; int b = (i+1)%7; if(e[i][a] < -5e17 && e[i][b] < -5e17) continue; if(e[i][a] >= -5e17 && e[i][b] >= -5e17) continue; if(e[i][a] >= -5e17){ e[i][b] = c[i]-e[i][a]; } else{ e[i][a] = c[i]-e[i][b]; } } } ll dmn = -1e18,dmx = 1e18; rep(i,7){ if(e[i][(i+1)%7]<0){ ll x = e[i][(i+1)%7]+100000000000000000LL; dmx = min(dmx,x); } else{ ll x = e[i][(i+1)%7]-100000000000000000LL; dmn = max(dmn,-x); } } rep(i,7){ if(e[(i+1)%7][i]<0){ ll x = e[(i+1)%7][i]+100000000000000000LL; dmx = min(dmx,x); } else{ ll x = e[(i+1)%7][i]-100000000000000000LL; dmn = max(dmn,-x); } } if(dmn > dmx){ puts("NO"); return 0; } if(dmx - dmn >= 1000){ puts("YES"); return 0; } for(ll d=dmn;d<=dmx;d++){ bool edge[7][7]={}; rep(i,7){ if(e[(i+1)%7][i]<0){ ll x = e[(i+1)%7][i]+100000000000000000LL; if(x-d > 0) edge[i][(i+1)%7] = edge[(i+1)%7][i] = 1; } else{ ll x = e[(i+1)%7][i]-100000000000000000LL; if(x+d > 0) edge[i][(i+1)%7] = edge[(i+1)%7][i] = 1; } if(e[i][(i+1)%7]<0){ ll x = e[i][(i+1)%7]+100000000000000000LL; if(x-d > 0) edge[i][(i+1)%7] = edge[(i+1)%7][i] = 1; } else{ ll x = e[i][(i+1)%7]-100000000000000000LL; if(x+d > 0) edge[i][(i+1)%7] = edge[(i+1)%7][i] = 1; } } bool used[7]={}; rep(i,7){ if(used[i]) continue; queue<int>que; que.push(i); int cnt = 0; while(!que.empty()){ int q = que.front(); que.pop(); if(used[q]) continue; used[q] = 1; cnt++; rep(x,7){ if(edge[x][q] && !used[x]){ que.push(x); } } } if(i && cnt > 1) goto fail; } puts("YES"); return 0; fail:; } puts("NO"); }
Submission Info
Submission Time | |
---|---|
Task | F - 歩くピアニスト |
User | IH19980412 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 3079 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 |