#include "rotate.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> vdebug;
/*void rotate(vector<int> t, int x)
{
for(int i : t) vdebug[i] = (vdebug[i] + x)%50000;
for(int i : vdebug) cout<<i<<" ";
cout<<endl;
}*/
int polar(int x)
{
return (x + 25000)%50000;
}
void energy(int n, vector<int> v)
{
vector<pair<int, int>> to, bo, le, ri;
for(int i = 0; i < n; i++){
if(v[i] == 0) to.push_back({v[i], i});
else if(v[i] < 25000) ri.push_back({v[i], i});
else if(v[i] == 25000) bo.push_back({v[i], i});
else le.push_back({v[i], i});
}
sort(le.begin(), le.end()); sort(ri.begin(), ri.end());
int topval = 50000, botval = 25000;
while(le.size() > 0 && ri.size() > 0){
if(le.size() + bo.size() > ri.size() + to.size()){
swap(le, ri); swap(bo, to);
swap(topval, botval);
}
//right is more than left
pair<int, int> x = le[le.size()-1];
pair<int, int> y = ri[ri.size()-1];
if(botval - y.first < topval - x.first){
rotate({y.second}, botval - y.first);
ri.pop_back(); bo.push_back(y);
}
else if(le.size() + bo.size() < ri.size() + to.size()){
rotate({y.second}, botval - y.first);
ri.pop_back(); bo.push_back(y);
}
else{
rotate({y.second}, polar(x.first) - y.first);
rotate({x.second, y.second}, topval - x.first);
le.pop_back(); ri.pop_back(); bo.push_back(y); to.push_back(x);
}
}
if(topval != 50000){
swap(le, ri); swap(bo, to);
swap(topval, botval);
}
while(le.size() > 0){
pair<int, int> x = le[le.size() - 1]; le.pop_back();
if(to.size() <= bo.size() + le.size()){
rotate({x.second}, topval - x.first);
to.push_back(x);
}
else{
rotate({x.second}, topval - x.first + 25000);
bo.push_back(x);
}
}
while(ri.size() > 0){
pair<int, int> x = ri[ri.size() - 1]; ri.pop_back();
if(bo.size() <= to.size() + ri.size()){
rotate({x.second}, botval - x.first);
bo.push_back(x);
}
else{
rotate({x.second}, botval - x.first + 25000);
to.push_back(x);
}
}
//cerr<<"A"<<bo.size()<<" "<<to.size()<<endl;
if(bo.size() < to.size()) swap(bo, to);
while(bo.size() > to.size()){
pair<int, int> x = bo[bo.size()-1]; bo.pop_back();
rotate({x.second}, 25000);
}
}
/*signed main()
{
int n; cin>>n;
vector<int> v(n);
for(int i = 0; i < n; i++) cin>>v[i];
vdebug = v;
energy(n, v);
for(int i : vdebug) cout<<i<<" ";
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |