CSES - Datatähti 2017 alku - Results
Submission details
Task:Maalarit
Sender:mangolassi
Submission time:2016-10-04 23:50:23 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED25
#3ACCEPTED31
#4ACCEPTED32
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.05 s1details
#7ACCEPTED0.05 s2details
#8ACCEPTED0.06 s2details
#9ACCEPTED0.06 s2details
#10ACCEPTED0.05 s2details
#11ACCEPTED0.05 s2details
#12ACCEPTED0.06 s2details
#13ACCEPTED0.01 s3details
#14ACCEPTED0.06 s3details
#15ACCEPTED0.05 s3details
#16ACCEPTED0.06 s3details
#17ACCEPTED0.05 s3details
#18ACCEPTED0.05 s3details
#19ACCEPTED0.13 s4details
#20ACCEPTED0.13 s4details
#21ACCEPTED0.10 s4details
#22ACCEPTED0.10 s4details
#23ACCEPTED0.11 s4details
#24ACCEPTED0.08 s4details

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 1
if (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 costs
p.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 wall
long 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 interval
if (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 ...