Submission #143328

#	Time	Username	Problem	Language	Result	Execution time	Memory
143328		VladaMG98	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	115 ms	19320 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

const int MAXN = 200010;

int bit[MAXN];
void upd(int pos, int val) {
    while(pos < MAXN) {
        bit[pos] += val;
        pos += pos & -pos;
    }
}
int get(int pos) {
    int ret = 0;
    while(pos) {
        ret += bit[pos];
        pos -= pos & -pos;
    }
    return ret;
}

bool marked[MAXN];
int arr[MAXN];
vector<int> occurences[2 * MAXN];
long long count_swaps(std::vector<int> s) {
	int n = (int)s.size() / 2;
	int N = 2 * n;
	long long ans = 0;
	int pos = 1;
	for(int i = 1; i <= N; i++) {
        arr[i] = s[i - 1];
	}
	for(int i = N; i >= 1; i--) {
        //printf("hey\n");
        occurences[arr[i] + MAXN].push_back(i);
	}
	for(int _ = 0; _ < n; _++) {
        while(marked[pos]) {
            //printf("%d\n", pos);
            pos += 1;
        }
        int num = arr[pos];
        int target = -num;
        int where = occurences[target + MAXN].back();
       // printf("%d %d %d %d\n", pos, num, target, where);
        marked[pos] = true;
        marked[where] = true;
        occurences[target + MAXN].pop_back();
        occurences[num + MAXN].pop_back();
        int cur_pos = where + (get(MAXN - 1) - get(where));
        ans += cur_pos - (2 * _ + 2);
        if(num > 0) ans += 1;
        //printf("ans = %lld\n", ans);
        upd(where, 1);
	}
	return ans;
}

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