Submission #1209545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209545		khanhphucscratch	Rotating Lines (APIO25_rotate)	C++20	11 / 100	40 ms	3772 KiB

rotate

#include "rotate.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> vdebug;
/*int eng()
{
    int n = vdebug.size(), ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++) ans += min(abs(vdebug[i] - vdebug[j]), 50000-abs(vdebug[i] - vdebug[j]));
    }
    return ans;
}
void rotate(vector<int> t, int x)
{
    int re = eng();
    for(int i : t) vdebug[i] = (vdebug[i] + x)%50000;
    for(int i : vdebug) cout<<i<<" ";
    cout<<endl;
    if(eng() < re){cout<<"Energy decreased"; exit(0);}
}*/
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(le.size() + bo.size() < ri.size() + to.size()){
            rotate({y.second}, botval - y.first);
            ri.pop_back(); bo.push_back(y);
        }
        else if(botval - y.first < topval - x.first){
            rotate({x.second}, polar(y.first) - x.first);
            rotate({x.second, y.second}, botval - y.first);
            le.pop_back(); ri.pop_back(); bo.push_back(y); to.push_back(x);
        }
        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); ri.push_back(x);
    }
}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int rnd(int l, int r)
{
    int x = rng()%(r-l+1);
    return x+l;
}
/*signed main()
{
    int n = 2;
    while(true){
        vector<int> v(n);
        for(int i = 0; i < n; i++) v[i] = rnd(0, 49)*1000;
        vdebug = v;
        for(int i : vdebug) cout<<i<<" ";
        cout<<endl;
        energy(n, v);
        cout<<endl;
    }
}
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 11 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 26