Submission #298214

#	Time	Username	Problem	Language	Result	Execution time	Memory
298214		Abelyan	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	176 ms	73028 KiB

shoes

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

#define FOR(i,n) for (int i=0;i<(n);++i)


const int N=1e6+6;
priority_queue<int> aj[N],dz[N];
int fw[N];
int n;
int get(int ind){
	int ans=0;
	for(;ind>=0;ind=(ind&(ind+1))-1){
		ans+=fw[ind];
	}
	return ans;
}

void add(int ind,int val){
	for(;ind<n;ind=ind|(ind+1)){
		fw[ind]+=val;
	}
}
bool col[N];

long long count_swaps(vector<int> s) {
	n=s.size();
	FOR(i,n){
		if (s[i]<0){
			dz[-s[i]].push(-i);
		}
		else{
			aj[s[i]].push(-i);
		}
	}
	long long ans=0;
	int qan=0;
	FOR(i,n){
		if (col[i])continue;
		
		int j;
		if (s[i]<0){
			dz[-s[i]].pop();
			j=-aj[-s[i]].top();
			aj[-s[i]].pop();
		}
		if (s[i]>0){
			ans++;
			aj[s[i]].pop();
			j=-dz[s[i]].top();
			dz[s[i]].pop();

		}
		col[j]=true;

		ans+=j-2*qan-1+get(j);
		add(j,-1);
		add(0,1);
		qan++;
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:57:9: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |   ans+=j-2*qan-1+get(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