제출 #1206816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206816		TroySer	Rotating Lines (APIO25_rotate)	C++20	5 / 100	3097 ms	1592 KiB

rotate

#include "rotate.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll FULL_ROTATION = 50000;

ll energyCalc(vector<int> v) {

    ll totCost = 0;
    for (ll i = 0; i < v.size(); i++) {
        for (ll j = i + 1; j < v.size(); j++) {
            totCost += min((ll)abs(v[i] - v[j]), FULL_ROTATION - abs(v[i] - v[j]));
        }
    }

    return totCost;

}

void energy(int N, std::vector<int> v) {

    ll globalBest = 0;
    vector<pair<ll, ll> > instructions;

    for (ll currAngle = 0; currAngle < FULL_ROTATION; currAngle++) {

        ll currAlternative = currAngle + FULL_ROTATION/2;
        ll currEnergy = energyCalc(v);
        
        vector<int> currV;
        currV.reserve(N);
        for (ll i = 0; i < N; i++) currV.push_back(v[i]);

        vector<pair<ll, ll> > currentInstructions;

        for (ll currRod = 0; currRod < N; currRod++) {

            ll tmp = currV[currRod];

            currV[currRod] = currAngle;
            ll energyIncreaseAngle = energyCalc(currV);
            currV[currRod] = tmp;

            currV[currRod] = currAlternative;
            ll energyIncreaseAlt = energyCalc(currV);
            currV[currRod] = tmp;

            if (max(energyIncreaseAlt, energyIncreaseAngle) < currEnergy) continue;

            if (energyIncreaseAngle >= energyIncreaseAlt) {
                currentInstructions.push_back({currRod, currAngle - tmp});
                currV[currRod] = currAngle;
                currEnergy = energyIncreaseAngle;
            } else {
                currentInstructions.push_back({currRod, currAlternative - tmp});
                currV[currRod] = currAlternative;
                currEnergy = energyIncreaseAlt;
            }

        }

        if (currEnergy > globalBest) {
            globalBest = currEnergy;
            instructions = currentInstructions;
        }

    }

    for (auto [i, x]: instructions) {
        vector<int> theRod;
        theRod.push_back(i);
        rotate(theRod, (x + 50000) % 50000);
    }

    // rotate({0, 1}, 1500);
    // rotate({1}, 25);
}

• 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