Submission #227186

#	Time	Username	Problem	Language	Result	Execution time	Memory
227186		urd05	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1095 ms	13448 KiB

shoes

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

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

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);
        }
        else {
            mi[-v[i]].push_back(i);
        }
    }
    long long ret=0;
    int used=0;
    vector<int> big;
    int in=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+=pl[now][ind[now]]-mi[now][ind[now]]-1;
            big.push_back(pl[now][ind[now]]);
        }
        else {
            ret+=mi[now][ind[now]]-pl[now][ind[now]];
            big.push_back(mi[now][ind[now]]);
        }
        while (in<big.size()&&big[in]<min(pl[now][ind[now]],mi[now][ind[now]])) {
            in++;
            used--;
        }
        ret-=used;
        used++;
        ind[now]++;
    }
    return ret;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (ind[j]<pl[j].size()) {
                 ~~~~~~^~~~~~~~~~~~~
shoes.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (in<big.size()&&big[in]<min(pl[now][ind[now]],mi[now][ind[now]])) {
                ~~^~~~~~~~~~~

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