Submission #227190

#	Time	Username	Problem	Language	Result	Execution time	Memory
227190		urd05	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	219 ms	23772 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;
    set<int> s;
    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);
        s.insert(i);
    }
    long long ret=0;
    int used=0;
    for(int i=0;i<n;i++) {
        int mini=1e9;
        int pos=*s.begin();
        int now=v[pos-1];
        if (now<0) {
            now=-now;
        }
        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);
        s.erase(pl[now][ind[now]]);
        s.erase(mi[now][ind[now]]);
        ind[now]++;
    }
    return ret;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:46:13: warning: unused variable 'mini' [-Wunused-variable]
         int mini=1e9;
             ^~~~
shoes.cpp:44: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: 15 / 15