Submission #259194

#	Time	Username	Problem	Language	Result	Execution time	Memory
259194		algorithm16	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	393 ms	28328 KiB

shoes

#include "shoes.h"
#include<iostream>
#include<map>
#include<vector>
using namespace std;
typedef long long int llint;
llint fwt[200005],bio[200005];
vector <int> v;
void update(int x,int v) {
	for(x;x<200005;x+=x&-x) fwt[x]+=v;
}
llint query(int x) {
	llint ret=0;
	for(x;x>0;x-=x&-x) ret+=fwt[x];
	return ret;
}
map <int,vector <int> > m;
long long count_swaps(std::vector<int> s) {
	llint ret=0;
	for(int i=s.size()-1;i>=0;i--) {
		m[s[i]].push_back(i);
		update(i+1,1);
	}
	for(int i=0;i<s.size();i++) {
		if(bio[i]) continue;
		int ind=m[-s[i]].back();
		m[-s[i]].pop_back();
		m[s[i]].pop_back();
		ret+=query(ind)-query(i)-1+(s[i]>0);
		bio[ind]=1;
		update(ind+1,-1);
		update(i+1,-1);
		//cout << ret << "\n";
	}
	return ret;
}
/*int main()
{
	int n;
	cin >> n;
	for(int i=0;i<n;i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}
	cout << count_swaps(v);
	return 0;
}*/

Compilation message (stderr)

shoes.cpp: In function 'void update(int, int)':
shoes.cpp:10:7: warning: statement has no effect [-Wunused-value]
  for(x;x<200005;x+=x&-x) fwt[x]+=v;
       ^
shoes.cpp: In function 'llint query(int)':
shoes.cpp:14:7: warning: statement has no effect [-Wunused-value]
  for(x;x>0;x-=x&-x) ret+=fwt[x];
       ^
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  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