Submission #1209516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209516		Ludissey	Rotating Lines (APIO25_rotate)	C++20	13 / 100	3096 ms	11244 KiB

rotate

#include "rotate.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;

vector<int> pos;
const int HALF=50000;
const int ACUT=25000;

int calc(){
    long long res = 0;
    for (int i = 0; i < sz(pos); i++){
        for (int j = i + 1; j <  sz(pos); j++){
            int d=abs(pos[i]-pos[j]);
            res+=min(d, HALF-d);
        }
    }
    return res;
}
int eg=0;
map<int,int> mp;
void change(){
    for (int i = 0; i < sz(pos); i++)
    {
        if(mp[pos[i]]==0) continue;
        for (int j = 0; j < sz(pos); j++)
        {
            if(i==j) continue;
            if(mp[pos[j]]==0) continue;
            int p=pos[i];
            pos[i]=(pos[j]+ACUT)%HALF;
            int c=calc();
            if(eg<=c){
                eg=c;
                mp[p]--;
                mp[pos[j]]--;
                int df=(pos[i]-p);
                if(df<0) df+=HALF;
                rotate({(signed)i},(signed)df);
                return;
            }
            pos[i]=p;
        }
    }
}

void energy(signed n, std::vector<signed> v){
    for (int i = 0; i < sz(v); i++) pos.push_back(v[i]);
    eg=calc();
    int rs=n;
    for (int i = 0; i < sz(pos); i++) mp[pos[i]]++;
    for (int i = 0; i < sz(pos); i++)
    {
        if(mp[pos[i]]==0) continue;
        if(mp[(pos[i]+ACUT)%HALF]>0) {
            mp[pos[i]]--;
            mp[(pos[i]+ACUT)%HALF]--;
            rs-=2;
        }
    }
    while (rs>1)
    {
        change();
        rs-=2;
    }
    while(eg!=((n/2)*((n+1)/2))*ACUT){
        cerr << "NO";
    }
}

• 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