Submission #811027

#	Time	Username	Problem	Language	Result	Execution time	Memory
811027		Essa2006	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	359 ms	147956 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
#include <cstdio>
#include <cassert>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF firtst
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int pr=18, s_p=(1<<pr), e_p=(1<<(pr+1))-1;
vector<int>SS;
map<int, queue<int>>mp;
void pre(){
    SS.clear(), mp.clear();
    SS.resize(1<<(pr+1));
}
void update(int id, int u, int v, int l, int r){
    if(l>v || r<u)
        return;
    if(l>=u && r<=v){
        SS[id]++;
        return;
    }
    int md=(l+r)/2;
    update(id*2, u, v, l, md);
    update(id*2+1, u, v, md+1, r);
        
}
int get(int ind){
    ll res=SS[ind];
    while(ind/=2)
        res+=SS[ind];
    return res;
}
ll count_swaps(vector<int> A){
    int n=A.size();
    pre();
    ll ans=0;
    for(int i=0;i<n;i++){
        if(A[i]>0 && !mp[-A[i]].empty()){
            int u=mp[-A[i]].front();
            mp[-A[i]].pop();
            ans+=i-u-get(u+s_p)-1;
            if(u!=i-1)
                update(1, u+1+s_p, i-1+s_p, s_p, e_p);
        }
        else if(A[i]<0 && !mp[-A[i]].empty()){
            int u=mp[-A[i]].front();
            mp[-A[i]].pop();
            ans+=i-u-get(u+s_p);
            update(1, u+s_p, i-1+s_p, s_p, e_p);
        }
        else{
            mp[A[i]].push(i);
        }
    }
    return ans;
    
}
//ll count_swaps2(vector<int> A){
//    bool same=1;
//    int n=A.size();
//    for(int i=1;i<n;i++){
//        if(abs(A[i])!=abs(A[i-1]))
//            same=0;
//    }
//    if(n/2<=1000){
//        int ans=0;
//        for(int i=0;i<n;i++){
//            if(A[i]>0){
//                bool found=0;
//                int ind=0;
//                for(int j=0;j<i;j++){
//                    if(-A[j]==A[i] && A[j+1]!=-A[j]){
//                        found=1;
//                        ind=j;
//                        break;
//                    }
//                }
//                if(found){
//                    for(int j=i-1;j>ind;j--){
//                        swap(A[j], A[j+1]);
//                        ans++;
//                    }
//                }
//            }
//            else if(A[i]<0){
//                bool found=0;
//                int ind=0;
//                for(int j=0;j<i;j++){
//                    if(-A[j]==A[i] && (!j || A[j]!=-A[j-1])){
//                        found=1;
//                        ind=j;
//                        break;
//                    }
//                }
//                if(found){
//                    for(int j=i-1;j>=ind;j--){
//                        swap(A[j], A[j+1]);
//                        ans++;
//                    }
//                }
//            }
//        }
//        return ans;
//    }
//    if(n/2>1000 && !same){
//        ll ans=A.size()/2;
//        return ans*(ans-1)/2;
//    }
//    
//} 
// 
//int main() {
//    for(int k=1;k<=8;k++){
//        vector<int>S;
//        for(int i=1;i<=k;i++){
//            S.push_back(i);
//            S.push_back(-i);
//        }
//        sort(all(S));
//        do{
//            long long result1 = count_swaps(S), result2=count_swaps2(S);
//            if(result1!=result2){
//                cout<<S.size()<<endl;
//                for(int i=0;i<S.size();i++){
//                    cout<<S[i]<<' ';
//                }
//                cout<<endl;
//                cout<<"Cor "<<result2<<endl<<"Wro "<<result1;
//                return 0;
//            }
//        }
//        while(next_permutation(all(S)));
//    }
//}

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