Submission #852307

#	Time	Username	Problem	Language	Result	Execution time	Memory
852307		teo_thrash	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	57 ms	12852 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int maxn=2e5+5;
int bit[maxn];

void update(int idx, int delta){
    for(; idx<maxn; idx += (idx & -idx)){
        bit[idx]+=delta;
    }
}

ll query(int idx){
    ll sum=0;
    for(; idx>0; idx -= (idx & -idx)){
        sum+=bit[idx];
    }

    return sum;
}

ll query(int l, int r){
    return query(r-1)-query(l);
}

ll count_swaps(vector<int> a){
    ll ans=0;
    vector<pii> shoes[maxn];

    int n=a.size()/2;

    for(int i=0; i<a.size(); i++){
        shoes[abs(a[i])].pb({a[i], i});
    }

    vector<pii> pairs;

    for(int i=1; i<=a.size()/2; i++){
        sort(shoes[i].begin(), shoes[i].end());

        for(int j=0; j<shoes[i].size()/2; j++){
            int l=shoes[i][j].second;
            int r=shoes[i][j + (shoes[i].size()/2) ].second;

            if(l>r){
                swap(l, r);
                ans++;
            }

            pairs.pb({l+1, r+1});
        }
    }
    for(int i=1; i<=a.size(); i++){
        update(i, 1);
    }
    sort(pairs.begin(), pairs.end());

    for(auto p: pairs){
        ans+=query(p.first, p.second);

        update(p.first, -1);
        update(p.second, -1);
    }

    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0; i<a.size(); i++){
      |                  ~^~~~~~~~~
shoes.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=1; i<=a.size()/2; i++){
      |                  ~^~~~~~~~~~~~
shoes.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j=0; j<shoes[i].size()/2; j++){
      |                      ~^~~~~~~~~~~~~~~~~~
shoes.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=1; i<=a.size(); i++){
      |                  ~^~~~~~~~~~
shoes.cpp:34:9: warning: unused variable 'n' [-Wunused-variable]
   34 |     int n=a.size()/2;
      |         ^

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