Submission #1208562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208562		kunzaZa183	Rotating Lines (APIO25_rotate)	C++20	100 / 100	33 ms	2932 KiB

rotate

#include "rotate.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void energy(int n, vector<int> v) {
  const ll mod = 50000;

  vector<int> all(n);
  iota(all.begin(), all.end(), 0);
  sort(all.begin(), all.end(), [&](int a, int b) { return v[a] < v[b]; });

  // vector<bool> used(n);

  deque<int> left;
  vector<int> right;
  for (auto a : all) left.push_back(a);

  while (!left.empty()) {
    // int cur2 = left.back();
    // if (used[left.back()]) {
    //   left.pop_back();
    //   continue;
    // }

    if (v[left.back()] - v[left[0]] > mod / 2) {
      right.push_back(left.back());
      left.pop_back();
    } else
      break;
  }

  while (left.size() + right.size() >= 2) {
    if (left.empty()) {
      left.push_back(right.back());
      right.pop_back();
    }

    int cur = left.front();
    // used[left.front()] = 1;
    left.pop_front();

    while (!right.empty()) {
      if (v[right.back()] - v[cur] <= mod / 2) {
        left.push_back(right.back());
        right.pop_back();
      } else
        break;
    }

    if (left.size() >= right.size()) {
      if (left.empty()) break;
      rotate({cur}, (v[left.back()] - mod / 2 - v[cur] + mod) % mod);
      // used[left.back()] = 1;
      left.pop_back();
    } else {
      rotate({cur}, (v[right.back()] + mod / 2 - v[cur] + mod) % mod);
      right.pop_back();
    }
  }
}

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