제출 #297311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297311		shayan_p	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1049 ms	21496 KiB

shoes

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

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2e5 + 10;

vector<int> pos[maxn];
vector<bool> sgn[maxn];

ll sol(vector<bool> v){
    ll ans = 0;
    int x = 0;
    for(int i = 0; i < sz(v); i++){
	if(v[i] == 0)
	    x++;
	else
	    x--;
	if(i & 1)
	    ans+= abs(x);
	else
	    ans+= abs(x-1);
    }
    return ans / 2;
}
ll inv(vector<bool> v){ // 0, 1
    int c = 0;
    ll ans = 0;
    for(int x : v){
	if(x == 0)
	    ans+= c;
	else
	    c++;
    }
    return ans;
}
ll count_swaps(vector<int> a){
    ll ans = 0;
    for(int i = 0; i < sz(a); i++){
	pos[abs(a[i])].PB(i);
	sgn[abs(a[i])].PB(a[i] > 0);
    }    
    int n = sz(a) / 2;
    for(int i = 1; i <= n; i++){
	ans+= sol(sgn[i]);

	for(int j = i+1; j <= n; j++){

	    vector<bool> vec;
	    int pt1 = 0, pt2 = 0;
	    while(pt1 + pt2 < sz(pos[i]) + sz(pos[j])){
		if(pt2 == sz(pos[j]) || (pt1 != sz(pos[i]) && pos[i][pt1] < pos[j][pt2]))
		    vec.PB(0), pt1++;
		else
		    vec.PB(1), pt2++;
	    }

	    ll A = inv(vec);
	    for(int i = 0; i < sz(vec); i++)
		vec[i] = !vec[i];
	    ll B = inv(vec);

	    ans+= min(A, B);
	}
    }
    return ans;
}

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