제출 #1204985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204985		avighna	Rotating Lines (APIO25_rotate)	C++20	16 / 100	38 ms	2796 KiB

rotate

#include <bits/stdc++.h>

void rotate(std::vector<int> t, int x);

void energy(int n, std::vector<int> v) {
  if (n == 2) {
    if (v[0] < v[1]) {
      rotate({1}, 25000 - (v[1] - v[0]));
    } else {
      rotate({0}, 25000 - (v[0] - v[1]));
    }
    return;
  }
  if (*std::max_element(v.begin(), v.end()) < 25000) {
    std::vector<std::pair<int, int>> c;
    for (int i = 0; i < n; ++i) {
      c.push_back({v[i], i});
    }
    std::sort(c.begin(), c.end());
    int cur = 0;
    for (auto &[v, i] : c) {
      if (cur++ < n / 2) {
        rotate({i}, -v);
      } else {
        rotate({i}, 25000 - v);
      }
    }
    return;
  }

  auto get_energy = [&]() {
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        int c = std::abs(v[i] - v[j]);
        ans += std::min(c, 50000 - c);
      }
    }
    return ans;
  };
  int e = get_energy();
  while (true) {
    std::pair<int, std::pair<int, int>> best = {-1, {-1, -1}};
    for (int i = 0; i < n; ++i) {
      int cur_e = e;
      for (int k = 0; k < n; ++k) {
          int c = std::abs(v[i] - v[k]);
          cur_e -= std::min(c, 50000 - c);
        }
      for (int j = 0; j < 50000; ++j) {
        int del = j - v[i];
        v[i] += del;
        int old_e = cur_e;
        for (int k = 0; k < n; ++k) {
          int c = std::abs(v[i] - v[k]);
          cur_e += std::min(c, 50000 - c);
        }
        best = std::max(best, {cur_e, {i, del}});
        old_e = cur_e;
        v[i] -= del;
      }
    }
    if (best.first <= e) {
      break;
    }
    e = best.first;
    v[best.second.first] += best.second.second; 
    rotate({best.second.first}, best.second.second);
  }
}

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