Submission #549845

#	Time	Username	Problem	Language	Result	Execution time	Memory
549845		esomer	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	426 ms	35632 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>

using namespace std;

#define intt long long

struct segTree{
	vector<intt> v;
	intt size = 1;
	void init(intt n){
		while(size < n) size *= 2;
		v.assign(2 * size, 0LL);
	}

	void set(int i, int j, int x, int lx, int rx){
		if(rx - lx == 1){
			v[x] = j;
      return;
		}
		intt m = (lx + rx) / 2;
		if(i < m) set(i, j, 2 * x + 1, lx, m);
		else set(i, j, 2 * x + 2, m, rx);
		v[x] = v[2 * x + 1] + v[2 * x + 2];
	}

	void set(int i, int j){
		set(i, j, 0LL, 0LL, size);
	}

	intt sum(intt l, intt r, intt x, intt lx, intt rx){
		if(lx >= l && rx <= r){
			return v[x];
		}
		if(rx <= l || lx >= r) return 0;
		intt m = (lx + rx) / 2;
		intt s1 = sum(l, r, 2 * x + 1, lx, m);
		intt s2 = sum(l, r, 2 * x + 2, m, rx);
		return s1 + s2;
	}
	intt sum(int l, int r){
		return sum(l, r, 0, 0, size);
	}
};

long long count_swaps(vector<int> s) {
	intt ans = 0;
	segTree st;
	st.init(s.size());
	map<int, set<int>> siz;
	for(int i = 0; i < s.size(); i++){
		siz[s[i]].insert(i);
	}
	for(int i = 0; i < s.size(); i++){
		if(s[i] == 0) continue;
		int f = i;
		siz[s[i]].erase(siz[s[i]].begin());
		int sec = *siz[-s[i]].begin();
		siz[-s[i]].erase(siz[-s[i]].begin());
		ans += sec - f - 1 - st.sum(f, sec);
		st.set(sec, 1);
		s[sec] = 0;
		if(s[f] > 0) ans += 1;
	}
	return ans;
}

Compilation message (stderr)

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