Submission #2872864


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
// typedef __int128_t Int;
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
using pii = pair<int, int>;
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);

  int N;
  cin >> N;
  vector<int> v(N);
  rep(i, 0, N) { cin >> v[i]; }

  auto me = max_element(all(v));
  if (*me <= 0) {
    cout << *me << endl << N - 1 << endl;
    for (int i = N - 1; i > me - v.begin(); i--)
      cout << i + 1 << endl;
    loop(distance(v.begin(), me)) cout << 1 << endl;
    return 0;
  }

  vector<int> odd, even;
  int odd_sum = 0, even_sum = 0;
  rep(i, 0, N) {
    if (v[i] > 0)
      if (i & 1) {
        odd.push_back(i);
        odd_sum += v[i];
      } else {
        even.push_back(i);
        even_sum += v[i];
      }
  }
  cout << max(odd_sum, even_sum) << endl;
  vector<int> s = (odd_sum < even_sum ? even : odd);
  vector<bool> a(N, 0);
  for (auto e : s) {
    a[e] = 1;
  }

  vector<int> ans;
  auto f = [&](int x) {
    vector<bool> _a;
    if (x == 0) {
      rep(i, 1, a.size()) { _a.push_back(a[i]); }
    } else if (x == a.size() - 1) {
      rep(i, 0, a.size() - 1) { _a.push_back(a[i]); }
    } else {
      rep(i, 0, a.size()) {
        if (i == x - 1 or i == x + 1)
          continue;
        else if (i == x) {
          _a.push_back(a[i - 1]);

        } else
          _a.push_back(a[i]);
      }
    }
    swap(a, _a);
    ans.push_back(x);
  };

  while (a[0] == 0)
    f(0);
  while (a.back() == 0)
    f(a.size() - 1);

  int i = 1;
  while (a.size() > 1) {
    if (a[0] == a[2])
      f(1);
    else
      f(2);
  }

  cout << ans.size() << endl;
  for (auto e : ans)
    cout << e + 1 << endl;

  return 0;
}

Submission Info

Submission Time
Task E - Both Sides Merger
User norma
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2498 Byte
Status AC
Exec Time 3 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 4
AC × 57
Set Name Test Cases
Sample example_0, example_1, example_2, example_3
All allneg_0, allneg_1, allneg_2, bigans_0, bigans_1, bigans_2, bigans_3, bigans_4, bigans_5, bigans_6, bigans_7, bigans_8, bigans_9, example_0, example_1, example_2, example_3, maxrand_0, maxrand_1, maxrand_10, maxrand_11, maxrand_12, maxrand_13, maxrand_14, maxrand_15, maxrand_16, maxrand_17, maxrand_18, maxrand_19, maxrand_2, maxrand_20, maxrand_21, maxrand_22, maxrand_23, maxrand_24, maxrand_25, maxrand_26, maxrand_27, maxrand_28, maxrand_29, maxrand_3, maxrand_4, maxrand_5, maxrand_6, maxrand_7, maxrand_8, maxrand_9, rand_0, rand_1, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9
Case Name Status Exec Time Memory
allneg_0 AC 3 ms 256 KB
allneg_1 AC 3 ms 256 KB
allneg_2 AC 3 ms 256 KB
bigans_0 AC 3 ms 256 KB
bigans_1 AC 3 ms 256 KB
bigans_2 AC 3 ms 256 KB
bigans_3 AC 3 ms 256 KB
bigans_4 AC 3 ms 256 KB
bigans_5 AC 3 ms 256 KB
bigans_6 AC 3 ms 256 KB
bigans_7 AC 3 ms 256 KB
bigans_8 AC 3 ms 256 KB
bigans_9 AC 3 ms 256 KB
example_0 AC 1 ms 256 KB
example_1 AC 1 ms 256 KB
example_2 AC 1 ms 256 KB
example_3 AC 1 ms 256 KB
maxrand_0 AC 3 ms 256 KB
maxrand_1 AC 3 ms 256 KB
maxrand_10 AC 3 ms 256 KB
maxrand_11 AC 3 ms 256 KB
maxrand_12 AC 3 ms 256 KB
maxrand_13 AC 3 ms 256 KB
maxrand_14 AC 3 ms 256 KB
maxrand_15 AC 3 ms 256 KB
maxrand_16 AC 3 ms 256 KB
maxrand_17 AC 3 ms 256 KB
maxrand_18 AC 3 ms 256 KB
maxrand_19 AC 3 ms 256 KB
maxrand_2 AC 3 ms 256 KB
maxrand_20 AC 3 ms 256 KB
maxrand_21 AC 3 ms 256 KB
maxrand_22 AC 3 ms 256 KB
maxrand_23 AC 3 ms 256 KB
maxrand_24 AC 3 ms 256 KB
maxrand_25 AC 3 ms 256 KB
maxrand_26 AC 3 ms 256 KB
maxrand_27 AC 3 ms 256 KB
maxrand_28 AC 3 ms 256 KB
maxrand_29 AC 3 ms 256 KB
maxrand_3 AC 3 ms 256 KB
maxrand_4 AC 3 ms 256 KB
maxrand_5 AC 3 ms 256 KB
maxrand_6 AC 3 ms 256 KB
maxrand_7 AC 3 ms 256 KB
maxrand_8 AC 3 ms 256 KB
maxrand_9 AC 3 ms 256 KB
rand_0 AC 2 ms 256 KB
rand_1 AC 2 ms 256 KB
rand_2 AC 1 ms 256 KB
rand_3 AC 2 ms 256 KB
rand_4 AC 3 ms 256 KB
rand_5 AC 2 ms 256 KB
rand_6 AC 2 ms 256 KB
rand_7 AC 2 ms 256 KB
rand_8 AC 2 ms 256 KB
rand_9 AC 3 ms 256 KB