Submission #855809

#	Time	Username	Problem	Language	Result	Execution time	Memory
855809		Huseyn123	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	67 ms	21376 KiB

shoes

#include <bits/stdc++.h>
#define MAX 200001
#include "shoes.h"
using namespace std;
typedef long long ll;
ll sum[MAX],cnt=1;
void update(ll x,ll v){
    while(x<=cnt){
        sum[x]+=v;
        x+=x&-x;
    }
}
ll query(ll x){
    ll res=0;
    while(x>=1){
        res+=sum[x];
        x-=x&-x;
    }
    return res;
}
ll count_swaps(vector<int> s) {
	int n=s.size();
	cnt=n;
	ll res=0; 
	vector<vector<int>> c;
	vector<vector<int>> d;
	c.resize(n+1); 
	d.resize(n+1);
	int ind=1;
	for(auto x:s){
		if(x<0){
			c[-x].push_back(ind);
		}
		else{
			d[x].push_back(ind);
		}
		ind++;
	}
	vector<pair<int,int>> e; 
	for(int i=1;i<=n;i++){
		for(int j=0;j<c[i].size();j++){
			int h1,h2; 
			h1=c[i][j]; 
			h2=d[i][j]; 
			if(h1<h2){
				e.push_back(make_pair(h1,h2));
			}
			else{
				e.push_back(make_pair(h2,h1)); 
				res++;
			}
		}
	}
	sort(e.begin(),e.end()); 
	for(auto x:e){
		update(x.first,-1); 
		update(x.second,-1);
		res+=query(x.second)-query(x.first-1)+x.second-x.first+1;
	}
	return res;
}

Compilation message (stderr)

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

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