Submission #314517

#	Time	Username	Problem	Language	Result	Execution time	Memory
314517		jaaguptamme	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	105 ms	17780 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=400005;
int ar[N];
ll get(int p){
    ll ans=0;
    while(p){
        ans+=ar[p];
        p-=p&(-p);
    }
    return ans;
}
void add(int p,ll val){
    while(p<N){
        ar[p]+=val;
        p+=p&(-p);
    }
}
long long count_swaps(std::vector<int> s) {
    int n=s.size()/2;
    vector<pair<int,int>>g[N];
    for(int i=0;i<s.size();i++){
        g[abs(s[i])].push_back({s[i],i});
        add(i+1,1);
    }
    ll ans=0;
    vector<pair<int,int>>ns;
    for(int i=1;i<=n;i++){
        sort(g[i].begin(),g[i].end());
        int cnt=g[i].size()/2;
        for(int j=0;j<cnt;j++){
            int l=g[i][j].second;
            int r=g[i][j+cnt].second;
            if(l>r){
                ans++;
                swap(l,r);
            }
            ns.push_back({l+1,r+1});
        }
    }
    sort(ns.begin(),ns.end());
    for(auto el:ns){
        int l=el.first,r=el.second;
        ans+=get(r-1)-get(l);
        add(l,-1);add(r,-1);
    }
	return ans;
}
/*int main(){
    vector<int>ar={2,1,-1,-2};
    for(auto el:ar)cout<<el<<endl;
    count_swaps(ar);
    return 0;
}*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

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