Submission #227189

#	Time	Username	Problem	Language	Result	Execution time	Memory
227189		urd05	Arranging Shoes (IOI19_shoes)	C++14	85 / 100	41 ms	8184 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

vector<int> pl[100001];
vector<int> mi[100001];
int ind[100001];

struct FenwickTree {
    int tree[200405];
    int sum(int i) {
        int ret=0;
        while (i>0) {
            ret+=tree[i];
            i-=(i&-i);
        }
        return ret;
    }
    void update(int i,int x) {
        while (i<=200005) {
            tree[i]+=x;
            i+=(i&-i);
        }
    }
};

FenwickTree ft;

long long count_swaps(vector<int> v) {
    int n=v.size()/2;
    if (n>1000) {
        vector<int> pl;
        vector<int> mi;
        for(int i=0;i<2*n;i++) {
            if (v[i]>0) {
                pl.push_back(i);
            }
            else {
                mi.push_back(i);
            }
        }
        long long ret=0;
        int used=0;
        vector<int> big;
        int ind=0;
        for(int i=0;i<n;i++) {
            if (pl[i]>mi[i]) {
                ret+=pl[i]-mi[i]-1;
                big.push_back(pl[i]);
            }
            else {
                ret+=mi[i]-pl[i];
                big.push_back(mi[i]);
            }
            while (ind<big.size()&&big[ind]<min(pl[i],mi[i])) {
                ind++;
                used--;
            }
            ret-=used;
            used++;
        }
        return ret;
    }
    for(int i=0;i<2*n;i++) {
        if (v[i]>0) {
            pl[v[i]].push_back(i+1);
        }
        else {
            mi[-v[i]].push_back(i+1);
        }
    }
    for(int i=1;i<=2*n;i++) {
        ft.update(i,1);
    }
    long long ret=0;
    int used=0;
    for(int i=0;i<n;i++) {
        int now=0;
        int mini=1e9;
        for(int j=1;j<=n;j++) {
            if (ind[j]<pl[j].size()) {
                if (min(pl[j][ind[j]],mi[j][ind[j]])<mini) {
                    mini=min(pl[j][ind[j]],mi[j][ind[j]]);
                    now=j;
                }
            }
        }
        if (pl[now][ind[now]]>mi[now][ind[now]]) {
            ret+=ft.sum(pl[now][ind[now]]-1)-ft.sum(mi[now][ind[now]]);
        }
        else {
            ret+=ft.sum(mi[now][ind[now]]-1)-ft.sum(pl[now][ind[now]])+1;
        }
        ft.update(pl[now][ind[now]],-1);
        ft.update(mi[now][ind[now]],-1);
        ind[now]++;
    }
    return ret;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (ind<big.size()&&big[ind]<min(pl[i],mi[i])) {
                    ~~~^~~~~~~~~~~
shoes.cpp:80:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (ind[j]<pl[j].size()) {
                 ~~~~~~^~~~~~~~~~~~~
shoes.cpp:75:9: warning: unused variable 'used' [-Wunused-variable]
     int used=0;
         ^~~~

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