Submission #55457

#	Time	Username	Problem	Language	Result	Execution time	Memory
55457		dennisstar	물통 (KOI17_bucket)	C++11	100 / 100	19 ms	8924 KiB

bucket

#include <bits/stdc++.h>
int Dp1[100010][2], Dp2[100010][2];
int a, b, c, d;
int l(int x, int y) {return !y?x:l(y,x%y);}
int chk()
{
	if (c==0) return Dp2[d][0]?Dp2[d][0]:(1<<30);
	if (c==a) return Dp2[d][1]?Dp2[d][1]:(1<<30);
	if (d==0) return Dp1[c][0]?Dp1[c][0]:(1<<30);
	if (d==b) return Dp1[c][1]?Dp1[c][1]:(1<<30);
}
void f(int x, int y, int lev)
{
	if (chk()<=lev) return ;
	if (x!=a&&y==0) Dp1[x][0]=lev;
	if (x!=a&&y==b) Dp1[x][1]=lev;
	if (x==0&&y!=b) Dp2[y][0]=lev;
	if (x==a&&y!=b) Dp2[y][1]=lev;
	if (x==c&&y==d) return ;
	if (x!=a&&(!Dp2[y][1]||Dp2[y][1]>lev+1)) f(a,y,lev+1);
	if (x!=0&&(!Dp2[y][0]||Dp2[y][0]>lev+1)) f(0,y,lev+1);
	if (y!=b&&(!Dp1[x][1]||Dp1[x][1]>lev+1)) f(x,b,lev+1);
	if (y!=0&&(!Dp1[x][0]||Dp1[x][0]>lev+1)) f(x,0,lev+1);
	if (a>=x+y&&(!Dp1[x+y][0]||Dp1[x+y][0]>lev+1)) f(x+y,0,lev+1);
	if (a<x+y&&(!Dp2[x+y-a][1]||Dp2[x+y-a][1]>lev+1)) f(a,x+y-a,lev+1);
	if (b>=x+y&&(!Dp2[x+y][0]||Dp2[x+y][0]>lev+1)) f(0,x+y,lev+1);
	if (b<x+y&&(!Dp1[x+y-b][1]||Dp1[x+y-b][1]>lev+1)) f(x+y-b,b,lev+1);
}
int main()
{
	scanf("%d %d %d %d", &a, &b, &c, &d);
	if (!(a==c||c==0||b==d||d==0)) {printf("-1"); return 0;}
	int e=l(a,b);
	if (c%e||d%e) {printf("-1"); return 0;}
	a/=e,b/=e,c/=e,d/=e;
	Dp1[a][1]=Dp2[b][1]=2;
	Dp1[a][0]=Dp2[b][0]=1;
	if (c==0&&d==0) {printf("0"); return 0;}
	if ((c==0&&d==b)||(c==a&&d==0)) {printf("1"); return 0;}
	if (c==a&&d==b) {printf("2"); return 0;}
	f(0,0,0);
	printf("%d", chk()!=(1<<30)?chk():-1);
	return 0;
}

Compilation message (stderr)

bucket.cpp: In function 'int chk()':
bucket.cpp:11:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
bucket.cpp: In function 'int main()':
bucket.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &a, &b, &c, &d);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 34 / 34
• Subtask 4: 43 / 43