# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1205593 | khangrl | Rotating Lines (APIO25_rotate) | C++20 | 0 ms | 0 KiB |
#include "rotate.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
static long long calc_energy(){
long long res = 0;
for (int i = 0; i < (int) v.size(); i++){
for (int j = i + 1; j < (int) v.size(); j++){
int d = abs(v[i] - v[j]);
res += std::min(d, 50000 - d);
}
}
return res;
}
void energy(int n, std::vector<int> v){
if(calc_energy()==n*n/4*25000+n%2*n/2*25000){
return ;
}
vector <pair <int, int> > sorted;
vector <int> fh, sh;
map <int, int> mp;
for(int i=0; i<n; i++){
sorted.pb({v[i], i});
mp[i]=v[i];
}
sort(sorted.begin(), sorted.end());
for(int i=0; i<n/2+n%2; i++){
if(sorted[i].ff>0) fh.pb(sorted[i].ss);
}
int sum=0;
while(!fh.empty()){
rotate(fh, -(mp[fh[0]]-sum));
int temp=mp[fh[0]];
while(mp[fh[0]]==temp and !fh.empty()){
fh.erase(fh.begin());
}
sum+=mp[fh[0]];
}
int j=0;
for(int i=n/2+n%2; i<n; i++){
if(sorted[i].ff>25000){
if(j==0) j=i;
sh.pb(sorted[i].ss);
}
}
if(j==0){
j=n;
}
sum=0;
while(!sh.empty()){
rotate(sh, -(mp[sh[0]]-sum-25000));
int temp=mp[sh[0]];
while(mp[sh[0]]==temp and sh.size()!=0){
sh.erase(sh.begin());
}
sum+=mp[sh[0]];
}
for(int i=j-1; i>=n/2+n%2; i--){
sh.pb(sorted[i].ss);
}
sum=0;
while(!sh.empty()){
rotate(sh, (25000-mp[sh[0]])-sum);
int temp=mp[sh[0]];
while(mp[sh[0]]==temp and !sh.empty()){
sh.erase(sh.begin());
}
sum+=(25000-mp[sh[0]]);
}
return ;
}