Submission #143820

#	Time	Username	Problem	Language	Result	Execution time	Memory
143820		sasa	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	9 ms	5240 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;
			}
		}
		if(pos == -1){
			while(true){
				ans++;
			}
		}
		int l = min_l[pos];
		for(int i=l; i>cur; i++)
			swap(a[i], a[i - 1]), ans++;
		int r = min_r[pos] + (min_r[pos] < min_l[pos]);
		for(int i=r; i>cur+1; i++)
			swap(a[i], a[i - 1]), ans++;
	}
	return ans;
}

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