Submission #1367612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367612		nagorn_ph	Rotating Lines (APIO25_rotate)	C++20	0 / 100	1 ms	836 KiB

rotate

#include "rotate.h"
#include <bits/stdc++.h>
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()

using namespace std;

const int N = 2e5 + 5;
// const int inf = 1e18;

void energy(int n, std::vector<int> v){
    vector <bool> visited(n);
    for (int round = 0; round < n; round++) {
        if (round % 2) {
            int choose = 0;
            for (int i = 0; i < n; i++) {
                if (visited[i]) continue;
                int initcost = 0, newcost = 0;
                for (int j = 0; j < n; j++) {
                    if (i == j) continue;
                    initcost += min(abs(v[i] - v[j]), 50000 - abs(v[i] - v[j]));
                    newcost += v[j];
                }
                if (newcost >= initcost) {
                    choose = i;
                    rotate({choose}, 50000 - v[i]);
                    visited[i] = 1;
                    break;
                }
            }
        }
        else {
            int choose = 0;
            for (int i = 0; i < n; i++) {
                if (visited[i]) continue;
                int initcost = 0, newcost = 0;
                for (int j = 0; j < n; j++) {
                    if (i == j) continue;
                    initcost += min(abs(v[i] - v[j]), 50000 - abs(v[i] - v[j]));
                    newcost += min(abs(25000 - v[j]), 50000 - abs(25000 - v[j]));
                }
                if (newcost >= initcost) {
                    choose = i;
                    rotate({choose}, (25000 - v[i] + 50000) % 50000);
                    visited[i] = 1;
                    break;
                }
            }
        }
    }
}

/*
25000*n*n/4 = 6250n^2
what if we distribute?
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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