Maalarit

#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;
  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";
  for (int is = 0; is < count;) {
    bool first = true;
    int im = 0;
    int ie = is;
    for (; ie < count; ++ie) {
      if (heights[ie] <= gb) break;
      if (heights[ie] > im) { im = heights[ie]; first = ((ie - is) % 2 == 0); }
    }
    bool parity = true;
    for (int i = is; i < ie; i += 1, parity = !parity) {
      if ((parity && first) || (!parity && !first)) {
        std::cout << "1 ";
      } else {
        std::cout << "2 ";
      }
    }
    if (ie < count) {
      std::cout << "3 ";
    }
    is = ie + 1;
  }
  std::cout << "\n";
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: WRONG ANSWER

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED

Test 18

Group: 3

Verdict: ACCEPTED

Test 19

Group: 4

Verdict: ACCEPTED

Test 20

Group: 4

Verdict: ACCEPTED

Test 21

Group: 4

Verdict: ACCEPTED

Test 22

Group: 4

Verdict: ACCEPTED

Test 23

Group: 4

Verdict: ACCEPTED

Test 24

Group: 4

Verdict: ACCEPTED