Submission #1211051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211051		abczz	Rotating Lines (APIO25_rotate)	C++20	5 / 100	3093 ms	4656 KiB

rotate

#include "rotate.h"
#include <vector>
#include <iostream>
#include <deque>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

void energy(int n, std::vector<int> v){
  ll u = v[0];
  deque <ll> dq[2];
  vector <int> Q;
  for (int i=0; i<n; ++i) {
    Q.push_back(i);
    (v[i] += (50000-u)) %= 50000;
  }
  rotate(Q, 50000-u);
  vector <array<ll, 2>> V;
  for (int i=1; i<n; ++i) {
    V.push_back({v[i], i});
  }
  sort(V.begin(), V.end());
  ll a[2] = {1, 0};
  for (auto [x, y] : V) {
    if (x == 0 && a[0] < (n+1)/2) ++a[0];
    else if (x == 25000 && a[1] < (n+1)/2) ++a[1];
    else if (x <= 25000) dq[0].push_back(y);
    else dq[1].push_back(y);
  }
  ll z = 25000;
  if (a[0] < a[1]) {
    z = 0, swap(dq[0], dq[1]);
    swap(a[0], a[1]);
  }
  while (!dq[0].empty() || !dq[1].empty()) {
    if (dq[0].size() == dq[1].size() && a[0] == a[1]) {
      auto u = dq[0].back();
      dq[0].pop_back();
      auto x = dq[1].back();
      dq[1].pop_back();
      ll w = min((50000+z-v[u]) % 50000, (50000+(z^25000)-v[x]) % 50000);
      v[u] += w, v[x] += w;
      if (w) rotate({(int)u, (int)x}, w);
      if (v[u] != z) dq[0].push_back(u);
      else ++a[1];
      if (v[x] != z^25000) dq[1].push_back(x);
      else ++a[0];
    }
    else if (dq[0].size() >= dq[1].size()) {
      auto u = dq[0].back();
      dq[0].pop_back();
      if (v[u] != z) rotate({(int)u}, (50000+z-v[u]) % 50000);
      ++a[1];
    }
    else {
      auto u = dq[1].front();
      dq[1].pop_front();
      if (v[u] != z) rotate({(int)u}, (50000+z-v[u]) % 50000);
      ++a[1];
    }
    if (a[0] <= a[1]) {
      z ^= 25000;
      swap(dq[0], dq[1]);
      swap(a[0], a[1]);
    }
  }
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 26