Task: | Maalarit |
Sender: | Shrike |
Submission time: | 2016-10-16 19:34:54 +0300 |
Language: | C++ |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
#4 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.05 s | 1 | details |
#2 | WRONG ANSWER | 0.05 s | 1 | details |
#3 | WRONG ANSWER | 0.06 s | 1 | details |
#4 | WRONG ANSWER | 0.06 s | 1 | details |
#5 | WRONG ANSWER | 0.05 s | 1 | details |
#6 | WRONG ANSWER | 0.05 s | 1 | details |
#7 | WRONG ANSWER | 0.05 s | 2 | details |
#8 | WRONG ANSWER | 0.06 s | 2 | details |
#9 | WRONG ANSWER | 0.05 s | 2 | details |
#10 | WRONG ANSWER | 0.06 s | 2 | details |
#11 | WRONG ANSWER | 0.05 s | 2 | details |
#12 | WRONG ANSWER | 0.05 s | 2 | details |
#13 | WRONG ANSWER | 0.06 s | 3 | details |
#14 | WRONG ANSWER | 0.05 s | 3 | details |
#15 | WRONG ANSWER | 0.05 s | 3 | details |
#16 | WRONG ANSWER | 0.06 s | 3 | details |
#17 | WRONG ANSWER | 0.05 s | 3 | details |
#18 | WRONG ANSWER | 0.05 s | 3 | details |
#19 | WRONG ANSWER | 0.30 s | 4 | details |
#20 | WRONG ANSWER | 0.28 s | 4 | details |
#21 | WRONG ANSWER | 0.31 s | 4 | details |
#22 | WRONG ANSWER | 0.29 s | 4 | details |
#23 | WRONG ANSWER | 0.29 s | 4 | details |
#24 | WRONG ANSWER | 0.28 s | 4 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:110:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (i = 0; i < tree[cur.first].size(); i++) { ^
Code
#include <iostream>#include <algorithm>#include <string>#include <vector>#include <sstream>#include <queue>#include <map>using namespace std;typedef long long ll;// If a is smaller, add zero#ifndef max_zero#define max_zero(a,b) (((a) > (b)) ? (a) : (0))#endif#ifndef max#define max(a,b) (((a) > (b)) ? (a) : (b))#endifintatoi (string c){stringstream s;int i;s << c;s >> i;return i;}/* goal is n+1, start 0 */vector<int>into_vec (string str, int size){vector<int> vec(size);istringstream ssin(str);int j = 0;while(ssin >> vec[j]) {j++;}return vec;vec.push_back(-1);}intmain(){ios_base::sync_with_stdio(0);cin.tie(0);string buf;int n, i, j;getline (cin, buf);n = atoi (buf);vector<pair<int, int>> tree[n*3];vector<int> vec;getline (cin, buf);vec = into_vec (buf, n);int c1, c2, c3;c1 = vec[0];c2 = 0;c3 = 0;tree[0].push_back({n+1, vec[1]});tree[0].push_back({1+(n*2), vec[1]});tree[n+1].push_back({2, vec[2]});tree[n+1].push_back({2+(n*2), vec[2]});tree[(2*n)+1].push_back({2, vec[2]});tree[(2*n)+1].push_back({2+n, vec[2]});for (i = 2; i < n-1; i++) {tree[i].push_back({n+i+1, vec[i+1]});tree[i].push_back({(2*n)+i+1, vec[i+1]});tree[n+i].push_back({i+1, vec[i+1]});tree[n+i].push_back({(2*n)+i+1, vec[i+1]});tree[(2*n)+i].push_back({n+i+1, vec[i+1]});tree[(2*n)+i].push_back({i+1, vec[i+1]});}tree[n-1].push_back({3*n, 0});tree[(2*n)-1].push_back({3*n, 0});tree[(3*n)-1].push_back({3*n, 0});/* Djikstra */priority_queue<pair<int, int> > frontier;frontier.push({0, c1});map<int, int> came_from;map<int, int> cost_so_far;came_from.insert(pair<int, int>(0, NULL));cost_so_far.insert(pair<int, int>(0, vec[0]));/* loop */while (!frontier.empty()) {auto cur = frontier.top();frontier.pop();if (cur.first == n*3) {break;}for (i = 0; i < tree[cur.first].size(); i++) {int tmp, next, cost;next = tree[cur.first][i].first;if (next < n) {j = 0;tmp = next;} else if (next < 2*n) {j = 1;tmp = next-n-1;} else {j = 2;tmp = next-(2*n)-1;}if (j == 0) {cost = c1;} else if (j == 1) {cost = c2;} else {cost = c3;}int new_cost = cost_so_far[cur.first] + max_zero(vec[tmp], cost);if (cost_so_far.find(next) == cost_so_far.end() || new_cost < cost_so_far[next]) {if (cost < vec[tmp]) {if (j == 0) {c1 = vec[tmp];priority_queue <pair<int, int> > f1;f1.push({0, 0});swap (f1, frontier);while (!f1.empty()) {auto nn = f1.top();f1.pop();if (nn.first < n) {frontier.push({nn.first, 0});} else {frontier.push(nn);}}} else if (j == 1) {c2 = vec[tmp];priority_queue <pair<int, int> > f1;f1.push({0, 0});swap (f1, frontier);while (!f1.empty()) {auto nn = f1.top();f1.pop();if (nn.first < 2*n && nn.first >= n) {frontier.push({nn.first, 0});} else {frontier.push(nn);}}} else {c3 = vec[tmp];priority_queue <pair<int, int> > f1;f1.push({0, 0});swap (f1, frontier);while (!f1.empty()) {auto nn = f1.top();f1.pop();if (nn.first < 3*n && nn.first >= 2*n) {frontier.push({nn.first, 0});} else {frontier.push(nn);}}}}int priority;cost_so_far.insert(pair<int, int>(next, new_cost));priority = new_cost;frontier.push({next, priority});came_from.insert(pair<int, int>(next, cur.first));}}}int cur = 3*n;vector<int> path = {cur};while (cur != 0) {cur = came_from[cur];path.push_back(cur);}cout << c1+c2+c3 << endl;for (i = path.size()-1; i > 0; i--) {int nx = path[i];if (nx < n) {cout << "1 ";} else if (nx < 2*n) {cout << "2 ";} else {cout << "3 ";}}return 0;}
Test details
Test 1
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 22 54 3 91 69 90 40 29 83 71 |
correct output |
---|
174 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
265 1 3 2 3 2 3 2 3 2 3 |
Test 2
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 49 3 96 38 90 18 92 74 83 1 |
correct output |
---|
170 3 1 2 1 2 1 2 1 2 1 2 |
user output |
---|
266 1 3 2 3 2 3 2 3 2 3 |
Test 3
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 46 3 41 30 16 17 12 93 80 81 |
correct output |
---|
173 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
267 1 3 2 3 2 3 2 3 2 3 |
Test 4
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 46 8 95 85 82 73 82 92 53 90 |
correct output |
---|
187 3 1 2 1 2 1 2 1 2 1 2 |
user output |
---|
282 1 3 2 3 2 3 2 3 2 3 |
Test 5
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 41 18 61 59 40 96 5 2 74 38 |
correct output |
---|
159 3 2 1 2 1 2 1 2 3 1 2 |
user output |
---|
266 1 3 2 3 2 3 2 3 2 3 |
Test 6
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
3 1 3 2 3 2 3 2 3 2 3 |
Test 7
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 1 39 94 5 24 84 84 10 78 61 38... |
correct output |
---|
193 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
291 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 8
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 31 73 18 88 49 28 66 5 32 48 9... |
correct output |
---|
199 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
299 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 9
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 45 56 36 60 31 10 23 79 29 17 ... |
correct output |
---|
198 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
298 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 10
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 1 77 70 62 21 68 40 54 90 62 1... |
correct output |
---|
194 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
294 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 11
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 4 47 41 81 56 64 12 10 20 100 ... |
correct output |
---|
189 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
297 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 12
Group: 2
Verdict: WRONG ANSWER
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
3 1 3 2 3 2 3 2 3 2 3 |
Test 13
Group: 3
Verdict: WRONG ANSWER
input |
---|
100 256160448 813097800 167146270 ... |
correct output |
---|
1929869257 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
-1388364394 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 14
Group: 3
Verdict: WRONG ANSWER
input |
---|
100 520002672 3542567 24668528 959... |
correct output |
---|
1946957555 3 1 2 3 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
-1352711208 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 15
Group: 3
Verdict: WRONG ANSWER
input |
---|
100 483158423 780224665 844754665 ... |
correct output |
---|
1959373560 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
-1319608264 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 16
Group: 3
Verdict: WRONG ANSWER
input |
---|
100 969647264 128558017 889036329 ... |
correct output |
---|
1997942264 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
-1297771539 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 17
Group: 3
Verdict: WRONG ANSWER
input |
---|
100 745018527 400495893 635468795 ... |
correct output |
---|
1961391143 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
-1313943868 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 18
Group: 3
Verdict: WRONG ANSWER
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
3 1 3 2 3 2 3 2 3 2 3 |
Test 19
Group: 4
Verdict: WRONG ANSWER
input |
---|
100000 197349274 775463806 263930657 ... |
correct output |
---|
1999942635 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
-1295008371 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 20
Group: 4
Verdict: WRONG ANSWER
input |
---|
100000 102296405 34648120 320393597 9... |
correct output |
---|
1999930943 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
-1294992593 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 21
Group: 4
Verdict: WRONG ANSWER
input |
---|
100000 781254921 418252056 502363453 ... |
correct output |
---|
1999987794 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
-1294985102 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 22
Group: 4
Verdict: WRONG ANSWER
input |
---|
100000 849784881 230439009 455097426 ... |
correct output |
---|
1999979439 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
-1294995650 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 23
Group: 4
Verdict: WRONG ANSWER
input |
---|
100000 851456132 13422224 537539701 4... |
correct output |
---|
1999948226 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
-1295034174 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |
Test 24
Group: 4
Verdict: WRONG ANSWER
input |
---|
100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
2 3 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 ... |
user output |
---|
3 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ... |