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