Submission #667825

#	Time	Username	Problem	Language	Result	Execution time	Memory
667825		coding_snorlax	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	237 ms	274908 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
int N=200050;
long long int check_List[400050];
long long int BIT[400050]={0};
deque<int> positive[200060];
deque<int> negative[200060];
int List1[200006]={0};
void pre(vector<int> List){
    for(int i=0;i<(int)List.size();i++){
        if(List[i]>0){
            if((int)negative[List[i]].size()>0){
                List1[negative[List[i]].front()]=i;
                negative[List[i]].pop_front();
            }
            else{
                positive[List[i]].push_back(i);
            }
        }
        if(List[i]<0){
            if((int)positive[-List[i]].size()>0){
                List1[positive[-List[i]].front()]=i;
                positive[-List[i]].pop_front();
            }
            else{
                negative[-List[i]].push_back(i);
            }
        }
    }
    return;
}
void modify(int node,int num){
    for(int i=node;i<=N;i+=i&(-i)){
        BIT[i]+=num;
    }
}
long long int query(int node){
    long long int answer=0;
    for(int i=node;i>=1;i-=i&(-i)){
        answer+=BIT[i];
    }
    return answer;
}
long long int count_swaps(vector<int> s){
    pre(s);
    for(int i=1;i<=(int)s.size()+2;i++){
        modify(i,1);
    }
    long long int Count_answer=0;
    for(int i=0;i<(int)s.size();i++){
        if(List1[i]!=0){
            if(s[i]>0) Count_answer+=1;
            Count_answer+=query(List1[i]+1)-query(i+1)-1;
            modify(i+1,1);
            modify(List1[i]+2,-1);
        }
    }
    return Count_answer;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15