Submission #143828

#	Time	Username	Problem	Language	Result	Execution time	Memory
143828		sasa	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1075 ms	4272 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>
using namespace std;
//#define int long long
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;
#define X first
#define Y second
#define all(o) o.begin(), o.end()
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0)
const int maxn = 2e5 + 10;
int min_l[maxn], min_r[maxn];
int a[maxn];
long long count_swaps(vi s) {
	int n = s.size() / 2;
	for(int i=0; i<2*n; i++)
		a[i] = s[i];

	ll ans = 0;
	
	for(int cur=0; cur<2*n; cur+=2){
		memset(min_l, 63, sizeof min_l);
		memset(min_r, 63, sizeof min_r);
		for(int j=2*n-1; j>=cur; j--){
			int sz = abs(a[j]);
			if(a[j] < 0)
				min_l[sz] = j;
			else
				min_r[sz] = j;
		}
		int mn = 1e9, pos = -1;
		for(int i=1; i<=n; i++){
			int tmp = min_l[i] + min_r[i];
			if(min_l[i] > min_r[i])
				tmp++;
			if(tmp < mn){
				mn = tmp;
				pos = i;
			}
		}
		//cout << "BIA" << pos << endl;	
		int l = min_l[pos];
		//cout << "WTF" << l << endl;
		for(int i=l; i>cur; i--){
			swap(a[i], a[i - 1]);
			ans++;
		}
		//cout << "L" << l << endl;
		int r = min_r[pos];
		if(a[r] != pos)
			r++;
		for(int i=r; i>cur+1; i--)
			swap(a[i], a[i - 1]), ans++;
	}
	return ans;
}/*
int main(){
	int n;
	cin >> n;
	vi s;
	for(int i=0; i<2*n; i++){
		int x;
		cin >> x;
		s.push_back(x);
	}
	cout << count_swaps(s) << endl;
}*/

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