Submission #199326

#	Time	Username	Problem	Language	Result	Execution time	Memory
199326		mythos	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	5 ms	376 KiB

shoes

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

using namespace std;

struct Fenwick {
    vector<int> a;
    int n;

    Fenwick(int n): n(n), a(vector<int>(n, 0)) {}

    int get(int j) {
        int res = 0;
        for (; j >= 0; j = (j & (j + 1)) - 1) res += a[j];
        return res;
    }

    int get(int l, int r) {
        return (get(r) - get(l - 1));
    }

    void set(int id) {
        for (; id < n; id = id | (id + 1)) a[id]++;
    }
};

vector<int> create_ind(int n, vector<int> &s) {
    vector<int> ind(2 * n + 1);
    for (int i = 0; i < 2 * n; i++) ind[s[i] + n] = i;
    return ind;
}

long long count_adj(int n, vector<int> &s) {
    vector<int> id = create_ind(n, s);
    Fenwick fw = Fenwick(2 * n);
    long long ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (s[i] != 0) {
            int pos = id[n - s[i]];
            ans += pos - i - fw.get(i, pos) - (s[i] < 0 ? 1 : 0);
            s[pos] = 0;
            fw.set(pos);
        }
    }
    return ans;
}

void change(vector<int> &v) {
    int n = (int) v.size() / 2;
    vector<int> cnt(n, 0);

    for (int i = 0; i < 2 * n; i++) {
        if (v[i] > 0) cnt[v[i] - 1]++;
    }
    for (int i = 1; i < n; i++) cnt[i] += cnt[i - 1];

    vector<int> cntl = cnt, cntr = cnt;

    for (int i = 0; i < 2 * n; i++) {
        if (v[i] > 0) v[i] = (--cntr[v[i] - 1]) + 1;
        else v[i] -= - ((--cntl[-v[i] - 1]) + 1);
    }
}

long long count_swaps(vector<int> s) {
    change(s);
    int n = (int) s.size() / 2;
    return count_adj(n, s);
}

Compilation message (stderr)

shoes.cpp: In constructor 'Fenwick::Fenwick(int)':
shoes.cpp:8:9: warning: 'Fenwick::n' will be initialized after [-Wreorder]
     int n;
         ^
shoes.cpp:7:17: warning:   'std::vector<int> Fenwick::a' [-Wreorder]
     vector<int> a;
                 ^
shoes.cpp:10:5: warning:   when initialized here [-Wreorder]
     Fenwick(int n): n(n), a(vector<int>(n, 0)) {}
     ^~~~~~~

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