Untitled
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...