Untitled

 avatar
unknown
plain_text
2 years ago
3.5 kB
2
Indexable
#include <set>
using namespace std;
struct node{
    int id, per;
} pool[40000];
int countt;
node* newNode(){
    return &pool[countt++];
}
 
bool compare(node *a, node *b){
    if(a->per != b->per) return a->per > b->per;
        return a->id < b->id;
}
 
struct cmp{
    bool operator()(node *a, node *b){
        if(a->per != b->per) return a->per > b->per;
        return a->id < b->id;
    }
};
 
set<node*, cmp> sortNode[10];
set<node*, cmp>::iterator mid[10];
node* change[10][2];
int cnt[10];
int n, l, nl;
 
void init(int N, int L, int mAbility[])
{
    countt=0;
    n=N, l=L, nl=n/l;
    int c=0, s=0;
    for(int i=0;i<10;i++) sortNode[i].clear();
    for(int i=0;i<n;i++){
        if(c==nl){
            c=0;
            s++;
        }
        node *a=newNode();
        a->id=i;
        a->per=mAbility[i];
        sortNode[s].insert(a);
        c++;
    }
    for(int i=0;i<l;i++){
        auto it=sortNode[i].begin();
        for(int j=0;j<nl/2;j++) it++;
        mid[i]=it;
    }
 
}
 
int move()
{
    int ans=0;
 
    for(int i=0;i<10;i++){
        cnt[i]=0;
    }
    cnt[0]=-1, cnt[l-1]=1;
 
    for(int i=0;i<l;i++){
        if(i!=0){
            auto it1=sortNode[i].begin();
            change[i][0]=*it1;
            ans+=(*it1)->id;
            sortNode[i].erase(it1);
        }
        if(i!=l-1){
            auto it2=sortNode[i].end();
            it2--;
            change[i][1]=*it2;
            ans+=(*it2)->id;
            sortNode[i].erase(it2);
        }
    }
 
    for(int i=0;i<l;i++){
        if(i!=0){
            sortNode[i].insert(change[i-1][1]);
            if(compare(*mid[i], change[i-1][1])){
                cnt[i]++;
            }
            else{
                cnt[i]--;
            }
        }
        if(i!=l-1){
            sortNode[i].insert(change[i+1][0]);
            if(compare(*mid[i], change[i+1][0])){
                cnt[i]++;
            }
            else{
                cnt[i]--;
            }
        }
    }
    for(int i=0;i<l;i++){
        if(cnt[i]==-2){
            mid[i]--;
        }
        else if(cnt[i]==2){
            mid[i]++;
        }
    }
    return ans;
}
 
int trade()
{
    int ans=0;
    for(int i=0;i<l;i++) cnt[i]=0;
    for(int i=0;i<l;i++){
        if(i!=0){
            auto it1=sortNode[i].begin();
            change[i][0]=*it1;
            ans+= (*it1)->id;
            sortNode[i].erase(it1);
        }
        if(i!=l-1){
            auto it2=mid[i]++;
            change[i][1]=*it2;
            ans+=(*it2)->id;
            sortNode[i].erase(it2);
        }
    }
    sortNode[0].insert(change[1][0]);
    if(!compare(*mid[0], change[1][0])){
        mid[0]--;
    }
 
    for(int i=1;i<l-1;i++){
        sortNode[i].insert(change[i-1][1]);
        if(compare(*mid[i], change[i-1][1])){
            cnt[i]++;
        }
        else{
            cnt[i]--;
        }
 
        sortNode[i].insert(change[i+1][0]);
        if(compare(*mid[i], change[i+1][0])){
            cnt[i]++;
        }
        else{
            cnt[i]--;
        }
    }
    for(int i=1;i<l-1;i++){
        if(cnt[i]==-2){
            mid[i]--;
        }
        else if(cnt[i]==2){
            mid[i]++;
        }
    }
 
    sortNode[l-1].insert(change[l-2][1]);
    if(compare(*mid[l-1], change[l-2][1])){
        mid[l-1]++;
    }
    return ans;
}
Editor is loading...