Submission #288253

#	Time	Username	Problem	Language	Result	Execution time	Memory
288253		Mercenary	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	121 ms	24568 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;

int bit[maxn];
vector<int> val[maxn];

int n;
void update(int x , int val){
    for( ; x <= n ; x += x & -x)bit[x] += val;
}
int query(int x){
    int res = 0;
    for( ; x > 0 ; x &= x - 1)res += bit[x];
    return res;
}
int cnt[maxn];
bool used[maxn];
vector<int> pos[maxn] , neg[maxn];

long long count_swaps(std::vector<int> a) {
    n = a.size();
    for(int i = 0 ; i < n ; ++i){
        if(a[i] > 0)pos[a[i]].pb(i);
        else neg[-a[i]].pb(i);
    }
    for(int i = 1 ; i <= n ; ++i)reverse(pos[i].begin(),pos[i].end()) , reverse(neg[i].begin(),neg[i].end());
    ll res = 0;
    for(int i = 0 ; i < n ; ++i){
        if(used[i])continue;
        int val = abs(a[i]);
        int j = 0;
        if(a[i] > 0)res++ , j = neg[val].back();
        else j = pos[val].back();
        used[j] = 1;
        pos[val].pop_back();
        neg[val].pop_back();
        res += query(j + 1) + j - (query(i + 1) + i) - 1;
        update(i + 1 , 1);
        update(j + 2 , -1);
    }
    return res;
}

#ifdef LOCAL
#include "shoes.h"
#include <cstdio>
#include <cassert>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
	int n;
	assert(1 == scanf("%d", &n));
	vector<int> S(2 * n);
	for (int i = 0; i < 2 * n; i++)
		assert(1 == scanf("%d", &S[i]));
	fclose(stdin);

	long long result = count_swaps(S);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}
#endif // LOCAL

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