CSES - Siperia opettaa 3.0

CSES - Siperia opettaa 3.0 - Results

Submission details
Task:	Jump
Sender:	zxc
Submission time:	2016-07-29 14:44:53 +0300
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	100

Test results
test	verdict	time
#1	ACCEPTED	0.06 s	details
#2	ACCEPTED	0.06 s	details
#3	ACCEPTED	0.98 s	details
#4	ACCEPTED	0.95 s	details
#5	ACCEPTED	0.94 s	details
#6	ACCEPTED	0.97 s	details
#7	ACCEPTED	0.94 s	details
#8	ACCEPTED	1.01 s	details
#9	ACCEPTED	1.00 s	details
#10	ACCEPTED	0.95 s	details
#11	ACCEPTED	0.97 s	details
#12	ACCEPTED	0.99 s	details
#13	ACCEPTED	0.92 s	details
#14	ACCEPTED	0.96 s	details
#15	ACCEPTED	0.94 s	details
#16	ACCEPTED	0.50 s	details
#17	ACCEPTED	0.53 s	details
#18	ACCEPTED	0.21 s	details
#19	ACCEPTED	0.29 s	details
#20	ACCEPTED	0.14 s	details
#21	ACCEPTED	0.17 s	details
#22	ACCEPTED	0.18 s	details
#23	ACCEPTED	0.18 s	details
#24	ACCEPTED	0.17 s	details
#25	ACCEPTED	0.16 s	details
#26	ACCEPTED	0.17 s	details
#27	ACCEPTED	0.17 s	details
#28	ACCEPTED	0.17 s	details
#29	ACCEPTED	0.16 s	details
#30	ACCEPTED	0.17 s	details
#31	ACCEPTED	0.18 s	details
#32	ACCEPTED	0.18 s	details
#33	ACCEPTED	0.17 s	details
#34	ACCEPTED	0.17 s	details
#35	ACCEPTED	0.17 s	details
#36	ACCEPTED	0.17 s	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:28:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < jo.size(); ++i){
                                ^

Code

#include <bits/stdc++.h>
using namespace std;
int t[222];
const int N = 22000;
const int MN = 1e4+100;
const int R = 30000;
int dp[202020];
int main() {
    int n;
    cin>>n;
    for(int i = 0; i < n; ++i) {
	cin>>t[i];
    }
    vector<int> mov;
    for(int i = 0; i < n; ++i) {
	for(int j = i+1; j < n; ++j) {
	    mov.push_back(abs(t[i]-t[j]));
	}
    }
    sort(mov.begin(), mov.end());
    mov.erase(unique(mov.begin(), mov.end()), mov.end());
    //for(auto y: mov) cout<<y<<' ';
    //cout<<'\n';
    vector<int> jo;
    jo.push_back(0);
    for(int i = 0; i< 202020; ++i) dp[i] = 1e9;
    dp[R] = 0;
    for(int i = 0; i < jo.size(); ++i){
	int x = jo[i];
	for(int y: mov) {
	    for(int j = 0; j < 2; ++j) {
		int ux = x;
		if(j == 0) ux += 2*y;
		else ux -= 2*y;
		if(abs(ux) < N && dp[ux+R] == 1e9) {
		    dp[ux+R] = dp[x+R]+1;
		    jo.push_back(ux);
		}
	    }
	}
    }
    /*
    for(int i = 0; i < 10; ++i) {
	cout<<dp[R+i]<<' ';
    }
    cout<<'\n';
    return 0;
    */
    int q;
    cin>>q;
    for(int i = 0; i < q; ++i) {
	int s,tt;
	cin>>s>>tt;
	int ans = 1e9;
	ans = dp[R+abs(s-tt)]*2;
	//cout<<abs(s-tt)<<'\n';
	for(int i = 0; i < n; ++i) {
	    int ux = 2*t[i] - s;
	    //cout<<abs(ux-tt)<<'\n';
	    if(abs(ux-tt) < N) {
		ans = min(ans, 1 + dp[R+abs(ux-tt)]*2);
	    }
	}
	for(int i = 0; i < n; ++i) {
	    int ux = 2*t[i] - tt;
	    if(abs(ux-tt) < N) {
		ans = min(ans, 1 + dp[R+abs(ux-s)]*2);
	    }
	}
	if(ans >= 1e9) cout<<-1<<'\n';
	else
	cout<<ans<<'\n';
    }
 
}

Test details

Test 1

Verdict: ACCEPTED

input
`4 1 2 4 7 ...` view save

correct output
`-1 -1 2 2 -1 ...` view save

user output
`-1 -1 2 2 -1 ...` view save

Test 2

Verdict: ACCEPTED

input
`4 1 2 6 10 ...` view save

correct output
`-1 1 2 -1 1 ...` view save

user output
`-1 1 2 -1 1 ...` view save

Test 3

Verdict: ACCEPTED

input
`200 12 14 30 101 ...` view save

correct output
`2 2 1 2 2 ...` view save

user output
`2 2 1 2 2 ...` view save

Test 4

Verdict: ACCEPTED

input
`200 13 22 196 211 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
`2 2 2 2 2 ...` view save

Test 5

Verdict: ACCEPTED

input
`200 10 41 107 167 ...` view save

correct output
`2 1 2 2 2 ...` view save

user output
`2 1 2 2 2 ...` view save

Test 6

Verdict: ACCEPTED

input
`200 91 166 275 278 ...` view save

correct output
`2 2 2 3 2 ...` view save

user output
`2 2 2 3 2 ...` view save

Test 7

Verdict: ACCEPTED

input
`200 18 104 138 182 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
`2 2 2 2 2 ...` view save

Test 8

Verdict: ACCEPTED

input
`200 115 144 272 274 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
`2 2 2 2 2 ...` view save

Test 9

Verdict: ACCEPTED

input
`200 84 177 208 219 ...` view save

correct output
`2 2 2 2 1 ...` view save

user output
`2 2 2 2 1 ...` view save

Test 10

Verdict: ACCEPTED

input
`200 96 131 228 258 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
`2 2 2 2 2 ...` view save

Test 11

Verdict: ACCEPTED

input
`200 0 77 132 189 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
`2 2 2 2 2 ...` view save

Test 12

Verdict: ACCEPTED

input
`200 3 33 74 118 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
`2 2 2 2 2 ...` view save

Test 13

Verdict: ACCEPTED

input
`200 95 162 171 448 ...` view save

correct output
`-1 -1 2 2 2 ...` view save

user output
`-1 -1 2 2 2 ...` view save

Test 14

Verdict: ACCEPTED

input
`200 32 72 229 239 ...` view save

correct output
`2 -1 2 2 -1 ...` view save

user output
`2 -1 2 2 -1 ...` view save

Test 15

Verdict: ACCEPTED

input
`200 30 124 136 176 ...` view save

correct output
`2 -1 2 -1 2 ...` view save

user output
`2 -1 2 -1 2 ...` view save

Test 16

Verdict: ACCEPTED

input
`116 34 68 85 87 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
`2 2 2 2 2 ...` view save

Test 17

Verdict: ACCEPTED

input
`112 64 264 268 298 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
`2 2 2 2 2 ...` view save

Test 18

Verdict: ACCEPTED

input
`64 14 15 19 31 ...` view save

correct output
`8 6 10 4 6 ...` view save

user output
`8 6 10 4 6 ...` view save

Test 19

Verdict: ACCEPTED

input
`200 0 1 2 3 ...` view save

correct output
`14 14 8 6 40 ...` view save

user output
`14 14 8 6 40 ...` view save

Test 20

Verdict: ACCEPTED

input
`1 2231 100000 16 2 6 8 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` view save

Test 21

Verdict: ACCEPTED

input
`2 1091 2342 100000 1588 4004 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` view save

Test 22

Verdict: ACCEPTED

input
`3 144 151 440 100000 ...` view save

correct output
`168 99 87 262 16 ...` view save

user output
`168 99 87 262 16 ...` view save

Test 23

Verdict: ACCEPTED

input
`4 2388 2979 6715 8029 ...` view save

correct output
`10 52 47 56 77 ...` view save

user output
`10 52 47 56 77 ...` view save

Test 24

Verdict: ACCEPTED

input
`5 1371 1946 6455 6889 ...` view save

correct output
`24 6 15 25 26 ...` view save

user output
`24 6 15 25 26 ...` view save

Test 25

Verdict: ACCEPTED

input
`6 1026 1031 4929 5038 ...` view save

correct output
`18 9 11 12 8 ...` view save

user output
`18 9 11 12 8 ...` view save

Test 26

Verdict: ACCEPTED

input
`7 21 44 60 70 ...` view save

correct output
`16 20 16 20 10 ...` view save

user output
`16 20 16 20 10 ...` view save

Test 27

Verdict: ACCEPTED

input
`8 95 627 710 784 ...` view save

correct output
`6 4 5 5 6 ...` view save

user output
`6 4 5 5 6 ...` view save

Test 28

Verdict: ACCEPTED

input
`9 48 209 791 920 ...` view save

correct output
`3 4 3 6 6 ...` view save

user output
`3 4 3 6 6 ...` view save

Test 29

Verdict: ACCEPTED

input
`10 814 1017 1217 3259 ...` view save

correct output
`4 6 6 4 6 ...` view save

user output
`4 6 6 4 6 ...` view save

Test 30

Verdict: ACCEPTED

input
`2 6748 9615 100000 6956 7730 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` view save

Test 31

Verdict: ACCEPTED

input
`2 2955 5079 100000 5049 3601 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` view save

Test 32

Verdict: ACCEPTED

input
`2 8591 9235 100000 6759 9705 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` view save

Test 33

Verdict: ACCEPTED

input
`2 1847 2965 100000 6674 4858 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` view save

Test 34

Verdict: ACCEPTED

input
`2 2033 7688 100000 4427 4007 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` view save

Test 35

Verdict: ACCEPTED

input
`2 0 1 100000 3190 5237 ...` view save

correct output
`-1 -1 -1 4232 4266 ...` view save

user output
`-1 -1 -1 4232 4266 ...` view save

Test 36

Verdict: ACCEPTED

input
`2 9999 10000 100000 4761 947 ...` view save

correct output
`3814 1612 -1 -1 -1 ...` view save

user output
`3814 1612 -1 -1 -1 ...` view save

Siperia opettaa 3.0

Jump

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Tasks

Submissions (zxc)