Task: | Hiker Safety |
Sender: | Hannes Ihalainen |
Submission time: | 2017-10-31 21:34:03 +0200 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.06 s | details |
#2 | ACCEPTED | 0.05 s | details |
#3 | ACCEPTED | 0.05 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.05 s | details |
#6 | ACCEPTED | 0.04 s | details |
#7 | ACCEPTED | 0.05 s | details |
#8 | ACCEPTED | 0.04 s | details |
#9 | ACCEPTED | 0.05 s | details |
#10 | ACCEPTED | 0.11 s | details |
#11 | ACCEPTED | 0.08 s | details |
#12 | ACCEPTED | 0.05 s | details |
#13 | ACCEPTED | 0.04 s | details |
#14 | ACCEPTED | 0.04 s | details |
#15 | ACCEPTED | 0.10 s | details |
#16 | ACCEPTED | 0.06 s | details |
#17 | ACCEPTED | 0.07 s | details |
Code
#include <bits/stdc++.h> using namespace std; int B; int P; int K; int d[1111]; int dp[1111][1111]; int A[1111]; int V[1111]; int A2[1111]; int V2[1111]; vector<int> ans; int f(int a, int b) { if(dp[a][b] != -1) return dp[a][b]; if(b == P-1) { dp[a][b] = 1e9; return dp[a][b]; } if(a >= b) { dp[a][b] = -2; return dp[a][b]; } dp[a][b] = d[b] - d[a]; //personal space if(dp[a][b] <= 0) dp[a][b] = -2; int q = -1e9; if(abs(d[a+1]-d[b]) <= B) { q = max(f(a+1, b), q); } if(abs(d[a]-d[b+1]) <= B) { q = max(f(a, b+1), q); } dp[a][b] = min(q, dp[a][b]); if(abs(d[a]-d[b]) > B) dp[a][b] = -2; return dp[a][b]; } void g(int x) { if(x == 0) { if(V[x] == P-1) return; ans.push_back(x); V[x]++; return; } while(dp[V[x-1]+1][V[x]] >= max(A[x], A[x-1])) { g(x-1); if(V[x-1] == P-1) return; } if(V[x] == P-1) { return; } if(dp[V[x-1]][V[x]+1] >= max(A[x], A[x-1])) { ans.push_back(x); V[x]++; return; } cout<<"impossible\n"; exit(0); } int main(){ cin >> B; cin >> P; for (int i=0; i<P; ++i) cin >> d[i]; cin >> K; for (int i=0; i<K; ++i){ cin >> A[i] >> V[i]; --V[i]; V2[i] = V[i]; } memset(dp, -1, sizeof dp); for(int i = 0; i < P; ++i) { for(int j = 0; j < P; ++j) { if(dp[i][j] == -1) f(i, j); } } for(int i = K-1; i >= 0; --i) { while(V[i] != P-1) { g(i); } } for(auto x: ans) { V2[x]++; if (x+1<K && V2[x+1]!=P-1){ int dd=d[V2[x+1]]-d[V2[x]]; if (dd<max(A[x],A[x+1]) || dd>B){ while(1); //cout << "QAQ\n"; } } if (x>0){ int dd=d[V2[x]]-d[V2[x-1]]; if (dd<max(A[x-1], A[x]) || dd>B){ while(1); //cout << "QAQ\n"; } } } for(int i = 0; i < K; ++i) { if(V2[i] != P-1) { while(1); //cout<<"QAQ\n"; } } for(auto x: ans) { cout<<(x+1)<<' '; } cout<<'\n'; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
15000 1000 0 99 218 221 239 269 684 719 1... |
correct output |
---|
1 1 1 1 1 2 1 1 2 4 5 6 7 8 9 ... |
user output |
---|
1 1 1 1 1 2 1 1 2 2 1 1 1 2 1 ... |
Test 2
Verdict: ACCEPTED
input |
---|
15000 1000 0 548 712 779 815 978 1511 199... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 ... |
user output |
---|
13 13 13 13 12 1 1 1 1 1 1 1 1... |
Test 3
Verdict: ACCEPTED
input |
---|
15000 1000 0 277 451 479 672 1238 1604 19... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 4
Verdict: ACCEPTED
input |
---|
15000 1000 0 232 341 342 510 575 942 1137... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 5
Verdict: ACCEPTED
input |
---|
15000 1000 0 980 1535 1694 2048 2430 3117... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 6
Verdict: ACCEPTED
input |
---|
15000 1000 0 179 318 387 529 633 861 872 ... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 7
Verdict: ACCEPTED
input |
---|
15000 1000 0 170 309 371 844 1656 2162 23... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 8
Verdict: ACCEPTED
input |
---|
15000 1000 0 600 1543 1909 1913 2128 2272... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 9
Verdict: ACCEPTED
input |
---|
15000 1000 0 15 24 215 1035 1056 1064 140... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 10
Verdict: ACCEPTED
input |
---|
15000 1000 0 525 1663 1820 1879 3342 4726... |
correct output |
---|
263 615 615 615 615 615 615 61... |
user output |
---|
615 613 612 613 614 615 611 61... |
Test 11
Verdict: ACCEPTED
input |
---|
15000 1000 0 431 1256 1305 1530 3361 3445... |
correct output |
---|
620 620 619 619 619 619 618 61... |
user output |
---|
617 616 617 618 619 620 615 61... |
Test 12
Verdict: ACCEPTED
input |
---|
15000 1000 0 140 162 888 1550 1746 2010 2... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 13
Verdict: ACCEPTED
input |
---|
15000 1000 0 109 153 562 649 1211 1316 15... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 14
Verdict: ACCEPTED
input |
---|
15000 1000 0 73 75 315 351 976 1015 1389 ... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 15
Verdict: ACCEPTED
input |
---|
2 1000 0 1 2 3 4 5 6 7 8 9 10 11 12 1... |
correct output |
---|
999 998 997 998 996 997 995 99... |
user output |
---|
999 998 997 998 996 997 995 99... |
Test 16
Verdict: ACCEPTED
input |
---|
15000 1000 0 171 195 1219 1417 2558 2771 ... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
36 36 36 35 36 37 14 14 1 1 1 ... |
Test 17
Verdict: ACCEPTED
input |
---|
15000 1000 0 2 233 305 553 556 612 937 15... |
correct output |
---|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
23 1 1 1 1 1 1 1 1 1 1 1 1 1 1... |