제출 #1288841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288841		ghammazhassan	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	16 ms	2736 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define fi first
#define se second
const int N=1e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
int fn[N];
void add(int i,int x){
    if (i<N){
        fn[i]+=x;
        add(i+(i&-i),x);
    }
}
int pr(int i){
    if (i==0)return 0;
    return fn[i]+pr(i-(i&-i));
}
ll count_swaps(vector<int>a)
{   
    int n=a.size()/2;
    a.push_back(a[2*n-1]);
    for (int i=2*n-1;i>0;i--){
    	a[i]=a[i-1];
    }
    map<int,queue<int>>d;
    if (n>1000){
        bool f=1;
        for (int i=1;i<=n;i++){
            if (a[i]>0 or a[i]!=-a[i+n]){
                f=0;
            }
        }
        if (f){
            return n*(n-1)/2;
        }
        c=0;
        int j=1;
        for (int i=1;i<=2*n;i++){
            if (d[-a[i]].size()){
                c+=j-d[-a[i]].front();
                d[-a[i]].pop();
                if (a[i]>0)c--;
            }
            else{
                d[a[i]].push(j);
                j++;
            }
            // cout << c << endl;
        }
        return c;
    }
    for (int i=1;i<=2*n;i++){
        d[a[i]].push(i);
    }
    ll c=0;
    vector<pair<int,int>>k;
    for (int i=1;i<=2*n;i++){
        if (d[a[i]].size() and d[a[i]].front()==i){
            k.push_back({d[-a[i]].front()-i,i});
            d[a[i]].pop();
            d[-a[i]].pop();
        }
    }
    sort(k.begin(),k.end());
    for (int i=0;i<n;i++){
        c+=k[i].fi;
        if (a[k[i].se]<0)c--;
        int d=0;
        for (int j=0;j<i;j++){
            if (k[j].se>k[i].se and k[j].se<k[i].se+k[i].fi and !(k[j].se+k[j].fi<k[i].fi+k[i].se)){
                d++;
            }
            else if(!(k[j].se>k[i].se) and ((k[j].se+k[j].fi<k[i].fi+k[i].se) and k[j].se+k[j].fi>k[i].se)){
                d++;
            }
        }
        c-=d;
        // c-=pr(k[i].fi+k[i].se)-pr(k[i].se);
        // add(k[i].se,1);
        // add(k[i].se+k[i].fi,-1);
    }
    return c;
}

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