Submission #55457

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
55457	2018-07-07 14:55:52	dennisstar	물통 (KOI17_bucket)	C++11	100 / 100	19 ms	8924 KiB

bucket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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()
{
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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