Submission #1207374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207374		Mousa_Aboubaker	Rotating Lines (APIO25_rotate)	C++17	13 / 100	3095 ms	1348 KiB

rotate

#include "rotate.h"
#include <bits/stdc++.h>
using namespace std;

template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// #include <bits/stdc++.h>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// #define getrand(l, r) uniform_int_distribution<int>(l, r)(rng)

const long long infl = 1e18 + 1;
const int inf = 1e9 + 1;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const long double eps = 1e-7;
const int mod = 50000;

int add(int a, int b) { return (a + b) % mod; }
int sub(int a, int b) { return (a - b + mod) % mod; }
int mul(int a, int b) { return (int)((long long)a * b % mod); }
int pwr(int a, int b = mod - 2)
{
  int res = 1;
  for (; b > 0; b >>= 1, a = mul(a, a))
    if (b & 1)
      res = mul(res, a);
  return res;
}
int divi(int a, int b)
{
  return mul(a, pwr(b));
}
template <typename T>
bool chmax(T &a, T b)
{
  if (b > a)
  {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, T b)
{
  if (b < a)
  {
    a = b;
    return true;
  }
  return false;
}

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define SZ(x) (int)x.size()
#define vec vector
#define dbg(x) cout << (#x) << " : " << x << endl;
using ll = long long;
using ull = unsigned long long;

void energy(int n, vector<int> v)
{
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int l, int r)
       { return v[l] < v[r]; });
  // brute force, everytime I will try to move the last rod as long as it won't decrease the result
  ll curr = 0;
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
      curr += min(abs(v[ord[i]] - v[ord[j]]), 50000 - abs(v[ord[i]] - v[ord[j]]));
  int all = 0;
  // for (int _ = 0; _ < 3; _++)
  // {
  //   for (int i = n - 1; i >= 0; i--)
  //   {
  //     auto check = [&](int md) -> ll
  //     {
  //       ll curr2 = curr;
  //       for (int j = 0; j < n; j++)
  //         curr2 -= min(abs(v[ord[i]] - v[ord[j]]), mod - abs(v[ord[i]] - v[ord[j]]));
  //       int x = (v[ord[i]] + md) % mod;
  //       for (int j = 0; j < n; j++)
  //         if (i != j)
  //           curr2 += min(abs(x - v[ord[j]]), mod - abs(x - v[ord[j]]));
  //       return curr2;
  //     };
  //     int l = 1, r = 50000 - v[ord[i]] - 1, ans = 1;
  //     if(i != n - 1)
  //       r = v[ord[i + 1]] - v[ord[i]] - 1;
  //     while (l <= r)
  //     {
  //       int md = (l + r) / 2;
  //       int md2 = md - 1;
  //       int x1 = check(md);
  //       int x2 = check(md2);
  //       if (x1 > x2)
  //       {
  //         l = md + 1;
  //         ans = md;
  //       }
  //       else
  //       {
  //         r = md - 1;
  //       }
  //     }
  //     ans--;
  //     ll curr2 = curr;
  //     for (int j = 0; j < n; j++)
  //       curr2 -= min(abs(v[ord[i]] - v[ord[j]]), mod - abs(v[ord[i]] - v[ord[j]]));
  //     int x = (v[ord[i]] + ans) % mod;
  //     for (int j = 0; j < n; j++)
  //       if (i != j)
  //         curr2 += min(abs(x - v[ord[j]]), mod - abs(x - v[ord[j]]));
  //     v[ord[i]] = x;
  //     if (ans != 0)
  //     {
  //       rotate({ord[i]}, ans);
  //       all++;
  //       assert(all <= 2e6);
  //     }
  //   }
  // // }
  // //   for (int _ = 0; _ < 3; _++)
  // // {
  //   for (int i = n - 1; i >= 0; i--)
  //   {
  //     auto check = [&](int md) -> ll
  //     {
  //       ll curr2 = curr;
  //       for (int j = 0; j < n; j++)
  //         curr2 -= min(abs(v[ord[i]] - v[ord[j]]), mod - abs(v[ord[i]] - v[ord[j]]));
  //       int x = (v[ord[i]] - md) % mod;
  //       for (int j = 0; j < n; j++)
  //         if (i != j)
  //           curr2 += min(abs(x - v[ord[j]]), mod - abs(x - v[ord[j]]));
  //       return curr2;
  //     };
  //     int l = 1, r = 1, ans = 1;
  //     if(i)
  //       r = -v[ord[i - 1]] + v[ord[i]] - 1;
  //     while (l <= r)
  //     {
  //       int md = (l + r) / 2;
  //       int md2 = md - 1;
  //       int x1 = check(md);
  //       int x2 = check(md2);
  //       if (x1 > x2)
  //       {
  //         l = md + 1;
  //         ans = md;
  //       }
  //       else
  //       {
  //         r = md - 1;
  //       }
  //     }
  //     ans--;
  //     ll curr2 = curr;
  //     for (int j = 0; j < n; j++)
  //       curr2 -= min(abs(v[ord[i]] - v[ord[j]]), mod - abs(v[ord[i]] - v[ord[j]]));
  //     int x = (v[ord[i]] - ans) % mod;
  //     for (int j = 0; j < n; j++)
  //       if (i != j)
  //         curr2 += min(abs(x - v[ord[j]]), mod - abs(x - v[ord[j]]));
  //     v[ord[i]] = x;
  //     if (ans != 0)
  //     {
  //       rotate({ord[i]}, -ans);
  //       all++;
  //       assert(all <= 2e6);
  //     }
  //   }
  // }
  // int all = 0;
  for (int _ = 0; _ < 3; _++)
  {
    for (int i = n - 1; i >= 0; i--)
    {
      while (true)
      {
        for (int k = 10; k >= 0; k--)
        {
          int take = 1 << k;
          if (k >= 3)
          {
            take = (v[ord[i]] + v[ord[(i + 1) % n]]) * k / (k - 1) - 1;
            take %= mod;
          }
          if (take > 50000 or take <= 0)
            continue;
          while (true)
          {
            int x = (v[ord[i]] + take) % mod;
            ll curr2 = curr;
            for (int j = 0; j < n; j++)
            {
              curr2 -= min(abs(v[ord[i]] - v[ord[j]]), mod - abs(v[ord[i]] - v[ord[j]]));
            }
            int temp = v[ord[i]];
            v[ord[i]] = x;
            for (int j = 0; j < n; j++)
            {
              curr2 += min(abs(v[ord[i]] - v[ord[j]]), mod - abs(v[ord[i]] - v[ord[j]]));
            }
            if (curr2 <= curr)
            {
              v[ord[i]] = temp;
              break;
            }
            all++;
            assert(all <= 2e6);
            rotate({ord[i]}, take);
            curr = curr2;
          }
        }
        break;
      }
    }
    for (int i = 0; i < n; i++)
    {

      int tmp = i;
      while (true)
      {
        // i = n - i - 1;

        for (int k = 10; k >= 0; k--)
        {
          int take = 1 << k;
          if (k >= 3)
          {
            take = (v[ord[i]] + v[ord[(i - 1 + n) % n]]) * k / (k - 1) - 1;
            take %= mod;
          }
          if (take > 50000 or take <= 0)
            continue;
          while (true)
          {
            int x = (v[ord[i]] - take + mod) % mod;
            ll curr2 = curr;
            for (int j = 0; j < n; j++)
            {
              curr2 -= min(abs(v[ord[i]] - v[ord[j]]), mod - abs(v[ord[i]] - v[ord[j]]));
            }
            int temp = v[ord[i]];
            v[ord[i]] = x;
            for (int j = 0; j < n; j++)
            {
              curr2 += min(abs(v[ord[i]] - v[ord[j]]), mod - abs(v[ord[i]] - v[ord[j]]));
            }
            if (curr2 <= curr)
            {
              v[ord[i]] = temp;
              break;
            }
            curr = curr2;
            all++;
            assert(all <= 2e6);
            rotate({ord[i]}, -take);
          }
        }
        break;
      }
      i = tmp;
    }
  }
}

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