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;
  // 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 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: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

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