oj.uz

Submission #55457

# Submission time Handle Problem Language Result Execution time Memory
55457 2018-07-07T14:55:52 Z dennisstar None (KOI17_bucket) C++11
100 / 100
 19 ms 8924 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 2 ms 400 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 6 ms 1932 KB Output is correct
8 Correct 3 ms 1932 KB Output is correct
9 Correct 2 ms 1932 KB Output is correct
10 Correct 2 ms 1932 KB Output is correct
11 Correct 2 ms 1932 KB Output is correct
12 Correct 3 ms 1932 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 2 ms 400 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 6 ms 1932 KB Output is correct
8 Correct 3 ms 1932 KB Output is correct
9 Correct 2 ms 1932 KB Output is correct
10 Correct 2 ms 1932 KB Output is correct
11 Correct 2 ms 1932 KB Output is correct
12 Correct 3 ms 1932 KB Output is correct
13 Correct 2 ms 1932 KB Output is correct
14 Correct 3 ms 1932 KB Output is correct
15 Correct 3 ms 1932 KB Output is correct
16 Correct 2 ms 1932 KB Output is correct
17 Correct 2 ms 1932 KB Output is correct
18 Correct 3 ms 1932 KB Output is correct
19 Correct 4 ms 1932 KB Output is correct
20 Correct 3 ms 1932 KB Output is correct
21 Correct 3 ms 1932 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1932 KB Output is correct
2 Correct 2 ms 1932 KB Output is correct
3 Correct 3 ms 1932 KB Output is correct
4 Correct 3 ms 1932 KB Output is correct
5 Correct 2 ms 1932 KB Output is correct
6 Correct 3 ms 1932 KB Output is correct
7 Correct 3 ms 1932 KB Output is correct
8 Correct 2 ms 1932 KB Output is correct
9 Correct 2 ms 1932 KB Output is correct
10 Correct 2 ms 1932 KB Output is correct

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 2 ms 400 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 6 ms 1932 KB Output is correct
8 Correct 3 ms 1932 KB Output is correct
9 Correct 2 ms 1932 KB Output is correct
10 Correct 2 ms 1932 KB Output is correct
11 Correct 2 ms 1932 KB Output is correct
12 Correct 3 ms 1932 KB Output is correct
13 Correct 2 ms 1932 KB Output is correct
14 Correct 3 ms 1932 KB Output is correct
15 Correct 3 ms 1932 KB Output is correct
16 Correct 2 ms 1932 KB Output is correct
17 Correct 2 ms 1932 KB Output is correct
18 Correct 3 ms 1932 KB Output is correct
19 Correct 4 ms 1932 KB Output is correct
20 Correct 3 ms 1932 KB Output is correct
21 Correct 2 ms 1932 KB Output is correct
22 Correct 2 ms 1932 KB Output is correct
23 Correct 3 ms 1932 KB Output is correct
24 Correct 3 ms 1932 KB Output is correct
25 Correct 2 ms 1932 KB Output is correct
26 Correct 3 ms 1932 KB Output is correct
27 Correct 3 ms 1932 KB Output is correct
28 Correct 2 ms 1932 KB Output is correct
29 Correct 2 ms 1932 KB Output is correct
30 Correct 2 ms 1932 KB Output is correct
31 Correct 2 ms 1932 KB Output is correct
32 Correct 4 ms 1932 KB Output is correct
33 Correct 3 ms 1932 KB Output is correct
34 Correct 3 ms 1932 KB Output is correct
35 Correct 2 ms 1932 KB Output is correct
36 Correct 3 ms 1932 KB Output is correct
37 Correct 3 ms 1932 KB Output is correct
38 Correct 3 ms 1932 KB Output is correct
39 Correct 5 ms 1932 KB Output is correct
40 Correct 3 ms 1932 KB Output is correct
41 Correct 5 ms 2380 KB Output is correct
42 Correct 5 ms 2380 KB Output is correct
43 Correct 2 ms 2380 KB Output is correct
44 Correct 3 ms 2380 KB Output is correct
45 Correct 19 ms 8924 KB Output is correct
46 Correct 3 ms 1932 KB Output is correct