Task: | Maalarit |
Sender: | mangolassi |
Submission time: | 2016-10-04 23:50:23 +0300 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 25 |
#3 | ACCEPTED | 31 |
#4 | ACCEPTED | 32 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.06 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 1 | details |
#3 | ACCEPTED | 0.05 s | 1 | details |
#4 | ACCEPTED | 0.05 s | 1 | details |
#5 | ACCEPTED | 0.06 s | 1 | details |
#6 | ACCEPTED | 0.05 s | 1 | details |
#7 | ACCEPTED | 0.05 s | 2 | details |
#8 | ACCEPTED | 0.06 s | 2 | details |
#9 | ACCEPTED | 0.06 s | 2 | details |
#10 | ACCEPTED | 0.05 s | 2 | details |
#11 | ACCEPTED | 0.05 s | 2 | details |
#12 | ACCEPTED | 0.06 s | 2 | details |
#13 | ACCEPTED | 0.01 s | 3 | details |
#14 | ACCEPTED | 0.06 s | 3 | details |
#15 | ACCEPTED | 0.05 s | 3 | details |
#16 | ACCEPTED | 0.06 s | 3 | details |
#17 | ACCEPTED | 0.05 s | 3 | details |
#18 | ACCEPTED | 0.05 s | 3 | details |
#19 | ACCEPTED | 0.13 s | 4 | details |
#20 | ACCEPTED | 0.13 s | 4 | details |
#21 | ACCEPTED | 0.10 s | 4 | details |
#22 | ACCEPTED | 0.10 s | 4 | details |
#23 | ACCEPTED | 0.11 s | 4 | details |
#24 | ACCEPTED | 0.08 s | 4 | details |
Code
#include <iostream>#include <stack>inline long min(long a, long b) {return (a <= b ? a : b);}inline long max(long a, long b) {return (a >= b ? a : b);}inline long abs(long v) {return (v >= 0 ? v : -v);}// custom list in order to implement combining two lists.struct ListNode {long a;long b;ListNode* next;ListNode(long a_painter, long b_painter) {a = a_painter;b = b_painter;next = 0;}};struct List {ListNode* root;List() {root = 0;}void print() {ListNode* p = root;while(p != 0) {std::cout << "(" << p->a << "," << p->b << "), ";p = p->next;}std::cout << "\n";}void add(long a, long b, ListNode* previous) {ListNode* n = new ListNode(a,b);if (previous == 0) {n->next = root;root = n;} else {n->next = previous->next;previous->next = n;}}void add(ListNode* n, ListNode* previous) {if (previous == 0) {n->next = root;root = n;} else {n->next = previous->next;previous->next = n;}}List combine_worse(List other) {List result;ListNode* rl = 0;ListNode* otherNode = other.root;ListNode* thisNode = root;ListNode* temp = 0;while(true) {long a = max(thisNode->a, otherNode->a);long b = max(thisNode->b, otherNode->b);if (thisNode->a == a) {if (otherNode->a == a) {temp = otherNode;otherNode = otherNode->next;delete temp;}temp = thisNode;thisNode = thisNode->next;} else {temp = otherNode;otherNode = otherNode->next;}temp->a = a;temp->b = b;if (thisNode == 0 || otherNode == 0) {result.add(temp, rl);break;}long nb = max(thisNode->b, otherNode->b);if (nb == b) {continue;} else {result.add(temp, rl);rl = (rl == 0 ? result.root : rl->next);}}while(thisNode != 0) {temp = thisNode;thisNode = thisNode->next;delete temp;}while(otherNode != 0) {temp = otherNode;otherNode = otherNode->next;delete temp;}root = 0;other.root = 0;return result;}void combine_better(long a,long b) {if (root->a == a) {root->b = min(root->b, b);return;} else if (root->a > a) {if (root->b >= b) {if (root->next == 0) {root->a = a;root->b = b;return;}ListNode* temp = root;root = root->next;delete temp;}} else {if (b >= root->b) {return;}add(a,b,0);return;}ListNode* p = root;ListNode* c = root->next;while(c != 0 && c->a > a) {if (c->b >= b) {p->next = c->next;delete c;} else {p = c;}c = p->next;}if (c == 0) {ListNode* nn = new ListNode(a,b);p->next = nn;} else if (c->a == a) {c->b = min(b, c->b);} else if (c->b > b) {ListNode* nn = new ListNode(a,b);p->next = nn;nn->next = c;}return;}};// Augmented binary heap. Sorted like binary tree based on index, children have smaller height than their parents.// i_s is interval start, i_e its end and min the smallest value under a node.struct Node {long h;int i;long min;int i_s;int i_e;List list;Node* left;Node* right;Node* parent;Node(long height, int index) {h = height;i = index;min = h;i_s = index;i_e = index;left = 0;right = 0;parent = 0;}};struct TreeHeap {Node* root;TreeHeap() {root = 0;}Node* min_index(Node* n) {while(n->left != 0) {n = n->left;}return n;}void print(Node* n) {std::cout << n->h << "-" << n->min << "-" << n->i_s << "-" << n->i_e;if (n->left != 0) {std::cout << "(";print(n->left);if (n->right != 0) {std::cout << ",";print(n->right);}std::cout << ")";} else if (n->right != 0) {std::cout << "(";print(n->right);std::cout << ")";}}void print_tree() {if (root != 0) {print(root);}std::cout << "\n";}Node* next_index(Node* n) {if (n->right != 0) {return min_index(n->right);}while(n->parent != 0) {if (n == n->parent->right) {n = n->parent;} else {return n->parent;}}return 0;}void add(long h, int i) {Node* node = new Node(h,i);if (root == 0) {root = node;} else {Node* n = root;if (h >= root->h) {node->left = root;root->parent = node;root = node;return;}while (true) {if (n->right == 0 || n->right->h <= h) {if (n->right != 0) {n->right->parent = node;node->left = n->right;}n->right = node;node->parent = n;break;} else {n = n->right;}}}}};// We use the following strategy:// The highest one of any interval must go to either gardener 1 or 2. If it would go to gardener 3, we could// Reduce the cost of that interval by painting that piece of wood with painter 1 or 2.// If we paint it with painter 2, we can fill the rest of the interval with 1 and 2, reaching// Minimum value easily. If we paint it with painter 1, we'll handle both of the intervals caused// By splitting this one. This way we only need nlgn time in the average case, uneven splits// can mess with us though, making the performance more like n squared.// So first we find all combinations we can pay to the painters on a given interval,// With redundant options removed, and then we combine the results for two intervals.// When the interval is the whole wall, we can go through the list and choose the smallest price.// After we have calculated how much we need to pay to the painters, You can just fill all of the wall pieces// With height below or equal to painter 3's salary, and then add the two remaining painters on the intervals,// such that painter 2's salary is low enough.int main() {int count;std::cin >> count;// Special case with 1if (count == 1) {long h;std::cin >> h;std::cout << h << " 1\n";std::cout << "1\n";} else {long* heights = new long[count];TreeHeap th;for (int i = 0; i < count; ++i) {long h;std::cin >> h;th.add(h, i);heights[i] = h;}std::stack<Node*> p;p.push(th.root);while(p.size() > 0) {Node* n = p.top();bool complete = true;if (n->left != 0) {if ((n->left->i_s == n->left->i && n->left->left != 0)|| (n->left->i_e == n->left->i && n->left->right != 0)) {p.push(n->left);complete = false;} else {n->min = min(n->left->min, n->min);n->i_s = n->left->i_s;}}if (n->right != 0) {if ((n->right->i_s == n->right->i && n->right->left != 0)|| (n->right->i_e == n->right->i && n->right->right != 0)) {p.push(n->right);complete = false;} else {n->min = min(n->right->min, n->min);n->i_e = n->right->i_e;}}if (complete) p.pop();}// Initialization complete, now calculate costsp.push(th.root);while(p.size() > 0) {Node* n = p.top();if ((n->left == 0 && n->i != 0) || (n->right == 0 && n->i != (count-1)) || (n->parent != 0 && (abs(n->parent->i - n->i) == 1))) {long a = n->h;long b = 0;if ((n->i - n->i_s) % 2 == 1 && n->i_s != 0) {b = n->left->min;}if ((n->i_e - n->i) % 2 == 1 && n->i_e != (count-1)) {b = max(b, n->right->min);}n->list.add(a,b,0);p.pop();continue;}bool d = true;if (n->left != 0 && n->left->list.root == 0) {p.push(n->left);d = false;}if (n->right != 0 && n->right->list.root == 0) {p.push(n->right);d = false;}if (d) {p.pop();if (n->left != 0) {if (n->right != 0) {n->list = n->left->list.combine_worse(n->right->list);} else {n->list = n->left->list;}} else {if (n->right != 0) {n->list = n->right->list;} else {n->list.add(n->h, 0, 0);continue;}}// Handle case where we have the 2nd painter paint the walllong a = n->h;long b = 0;// If the distance is odd, we need a 3 somewhere, so we put it at the Minimum.// This however is not necessary if both ends of the interval aren't green.if ((n->i - n->i_s) % 2 == 1 && n->i_s != 0) {b = n->left->min;}if ((n->i_e - n->i) % 2 == 1 && n->i_e != count-1) {b = max(b, n->right->min);}n->list.combine_better(a,b);}}// Now with the costs generate a solution.ListNode* n = th.root->list.root;long cost = 10e10;long gc = th.root->h; long gb = 0; long ga = 0;while(n != 0) {if (n->a + n->b < cost) {ga = n->a;gb = n->b;cost = ga + gb;}n = n->next;}std::cout << gc + gb + ga << " " << (gb > 0 ? 3 : 2) << "\n";if (ga == gc) {for (int i = 0; i < count; ++i) {std::cout << i % 2 + 1 << " ";}std::cout << "\n";} else {int intervalStart = 0; int intervalEnd = 0; long intervalMin = 10e10; int minX = 0;for (int i = 0; i < count; ++i) {if (heights[i] > ga) {intervalEnd = i - 1;// Fill the intervalif (intervalStart == 0 || (intervalEnd - intervalStart) % 2 == 0) {for (int m = intervalStart; m <= intervalEnd; ++m) {std::cout << (((intervalEnd - m) % 2 == 0) ? "2 " : "1 ");}} else {for(int m = intervalStart; m < minX; ++m) {std::cout << (((m-intervalStart) % 2 == 0) ? "2 " : "1 ");}std::cout << "3 ";for(int m = minX + 1; m <= intervalEnd; ++m) {std::cout << (((intervalEnd - m) % 2 == 0) ? "2 " : "1 ");}}std::cout << "1 ";intervalStart = i + 1;intervalMin = 10e10;} else if (heights[i] < intervalMin) {intervalMin = heights[i];minX = i;}}for (int m = intervalStart; m <= count-1; ++m) {std::cout << (((m - intervalStart) % 2 == 0) ? "2 " : "1 ");}std::cout << "\n";}}}
Test details
Test 1
Group: 1
Verdict: ACCEPTED
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 |
---|
174 2 2 1 2 1 2 1 2 1 2 1 |
Test 2
Group: 1
Verdict: ACCEPTED
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 |
---|
170 2 1 2 1 2 1 2 1 2 1 2 |
Test 3
Group: 1
Verdict: ACCEPTED
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 |
---|
173 2 2 1 2 1 2 1 2 1 2 1 |
Test 4
Group: 1
Verdict: ACCEPTED
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 |
---|
187 2 1 2 1 2 1 2 1 2 1 2 |
Test 5
Group: 1
Verdict: ACCEPTED
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 |
---|
159 3 2 1 2 1 2 1 2 3 1 2 |
Test 6
Group: 1
Verdict: ACCEPTED
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 |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 7
Group: 2
Verdict: ACCEPTED
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 |
---|
193 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 8
Group: 2
Verdict: ACCEPTED
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 |
---|
199 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 9
Group: 2
Verdict: ACCEPTED
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 |
---|
198 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 10
Group: 2
Verdict: ACCEPTED
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 |
---|
194 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 11
Group: 2
Verdict: ACCEPTED
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 |
---|
189 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 12
Group: 2
Verdict: ACCEPTED
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 |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 13
Group: 3
Verdict: ACCEPTED
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 |
---|
1929869257 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 14
Group: 3
Verdict: ACCEPTED
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 |
---|
1946957555 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 15
Group: 3
Verdict: ACCEPTED
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 |
---|
1959373560 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 16
Group: 3
Verdict: ACCEPTED
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 |
---|
1997942264 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 17
Group: 3
Verdict: ACCEPTED
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 |
---|
1961391143 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 18
Group: 3
Verdict: ACCEPTED
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 |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 19
Group: 4
Verdict: ACCEPTED
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 |
---|
1999942635 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 20
Group: 4
Verdict: ACCEPTED
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 |
---|
1999930943 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 21
Group: 4
Verdict: ACCEPTED
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 |
---|
1999987794 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 22
Group: 4
Verdict: ACCEPTED
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 |
---|
1999979439 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 23
Group: 4
Verdict: ACCEPTED
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 |
---|
1999948226 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 24
Group: 4
Verdict: ACCEPTED
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 |
---|
2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |