Submission #227188

#	Time	Username	Problem	Language	Result	Execution time	Memory
227188		urd05	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1098 ms	14108 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;
    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:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (ind[j]<pl[j].size()) {
                 ~~~~~~^~~~~~~~~~~~~
shoes.cpp:42:9: warning: unused variable 'used' [-Wunused-variable]
     int used=0;
         ^~~~

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