Submission #200391

#	Time	Username	Problem	Language	Result	Execution time	Memory
200391		thiago4532	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	333 ms	274676 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 1e5 + 10;

#include <vector>
#define INF 0x3f3f3f3f

long long merge_sort(vector<int> &v){
    long long  inv=0;
    if(v.size()==1) return 0;


    vector<int> u1, u2;
    for(int i=0;i<(int)v.size()/2;i++){
        u1.push_back(v[i]);
    }
    for(int i=v.size()/2;i<(int)v.size();i++){
        u2.push_back(v[i]);
    }   

    inv+=merge_sort(u1);
    inv+=merge_sort(u2);

    u1.push_back(INF);
    u2.push_back(INF);

    int ini1=0, ini2=0;
    for(int i=0;i<(int)v.size();i++){
        if(u1[ini1]<=u2[ini2]){
            v[i]=u1[ini1];
            ini1++;
        }
        else{
            v[i]=u2[ini2];
            ini2++;
            inv+=u1.size()-ini1-1;
        }
    }

    return inv;
}

long long count_swaps(std::vector<int> s) {
	int n = s.size();
	vector< queue<int> > mapa(2*n);
	vector<int> pos(n), val(n);

	for (int i = 0; i < (int)s.size(); i++) {
		if (!mapa[ n - s[i] ].empty()) {
			int x = mapa[ n - s[i] ].front();
			mapa[n - s[i]].pop();

			pos[i] = x;
			pos[x] = i;
		}else mapa[ n + s[i] ].push(i);
	}

	int k = 1;
	for (int i = 0; i < (int)s.size(); i++) {
		if (val[ pos[i] ]){
			val[i] = val[ pos[i] ] + 1;
			if (s[i] < s[pos[i]])
				swap(val[i], val[pos[i]]);
		}
		else val[i] = k, k += 2;
	}

	long long sum = merge_sort(val);
	// for(auto & e : val)
	// 	cout << e << " ";
	// cout << "\n";

	return sum;
}

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