Guest User

1419D2

a guest
Sep 19th, 2020
5,833
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios_base::sync_with_stdio(false);
  6.     cin.tie(NULL);
  7.     cout.tie(NULL);
  8.     int n;
  9.     cin >> n;
  10.     vector<int> a(n);
  11.     for (int i = 0; i < n; ++i) {
  12.         cin >> a[i];
  13.     }
  14.     sort(a.begin(), a.end());
  15.     int l = 0, r = n + 1;
  16.     while (r - l > 1) {
  17.         int m = (l + r) / 2;
  18.         bool f = true;
  19.         if (2 * m + 1 > n) {
  20.             f = false;
  21.         }
  22.         else {
  23.             vector<int> b;
  24.             int pos_a = 0, pos_b = n - (m + 1);
  25.             for (int i = 0; i < 2 * m + 1; ++i) {
  26.                 if (i % 2 == 0) {
  27.                     b.emplace_back(a[pos_b]);
  28.                     ++pos_b;
  29.                 }
  30.                 else {
  31.                     b.emplace_back(a[pos_a]);
  32.                     ++pos_a;
  33.                 }
  34.             }
  35.             for (int i = 1; i < 2 * m + 1; i += 2) {
  36.                 if (b[i] >= b[i - 1] || b[i] >= b[i + 1])
  37.                     f = false;
  38.             }
  39.         }
  40.         if (f)
  41.             l = m;
  42.         else
  43.             r = m;
  44.     }
  45.     cout << l << endl;
  46.     vector<int> b;
  47.     int pos_a = 0, pos_b = n - (l + 1);
  48.     for (int i = 0; i < 2 * l + 1; ++i) {
  49.         if (i % 2 == 0) {
  50.             b.emplace_back(a[pos_b]);
  51.             ++pos_b;
  52.         }
  53.         else {
  54.             b.emplace_back(a[pos_a]);
  55.             ++pos_a;
  56.         }
  57.     }
  58.     for (int i = pos_a; i < n - (l + 1); ++i) {
  59.         b.emplace_back(a[i]);
  60.     }
  61.     for (auto &c : b) {
  62.         cout << c << " ";
  63.     }
  64. }
RAW Paste Data