oj.uz

Submission #145563

# Submission time Handle Problem Language Result Execution time Memory
145563 2019-08-20T11:59:18 Z surface03 None (KOI17_bucket) C++14
100 / 100
 17 ms 5168 KB 
#include<stdio.h>
 
const int LM=(int)1e5+5;
bool used[4][LM];
int a,b,c,d;
struct State{
    int L,R,S;
}que[LM*4];
int fr,re;
 
int push(int L,int R,int S){
    int i,j;
    if(L>=a)R+=L-a,L=a,i=1,j=R;
    else if(R>=b)L+=R-b,R=b,i=3,j=L;
    else if(L==0)i=0,j=R;
    else if(R==0)i=2,j=L;
    if(used[i][j])return 0;
    if(L==c&&R==d)return 1;
    used[i][j]=1;
    que[re++]={L,R,S};
    return 0;
}
 
int bfs(){
    push(0,0,0);
    if(c==0&&d==0)return 0;
    while(fr<re){
        State&t=que[fr++];
        if(push(0,t.R,t.S+1))return t.S+1;
        if(push(0,t.L+t.R,t.S+1))return t.S+1;
        if(push(a,t.R,t.S+1))return t.S+1;
        if(push(t.L,0,t.S+1))return t.S+1;
        if(push(t.L+t.R,0,t.S+1))return t.S+1;
        if(push(t.L,b,t.S+1))return t.S+1;
    }
    return -1;
}
int main(){
    scanf("%d%d%d%d",&a,&b,&c,&d);
    printf("%d",bfs());
}

Compilation message

bucket.cpp: In function 'int main()':
bucket.cpp:39:10: 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);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bucket.cpp: In function 'int push(int, int, int)':
bucket.cpp:17:17: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(used[i][j])return 0;
        ~~~~~~~~~^
bucket.cpp:17:17: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 3 ms 388 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 380 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #3
34.0 / 34.0

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

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 3 ms 388 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 380 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 256 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 380 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 10 ms 3068 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 2 ms 504 KB Output is correct
38 Correct 3 ms 632 KB Output is correct
39 Correct 3 ms 632 KB Output is correct
40 Correct 2 ms 472 KB Output is correct
41 Correct 3 ms 760 KB Output is correct
42 Correct 5 ms 1144 KB Output is correct
43 Correct 4 ms 888 KB Output is correct
44 Correct 3 ms 760 KB Output is correct
45 Correct 17 ms 5168 KB Output is correct
46 Correct 2 ms 256 KB Output is correct