제출 #1203165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203165		SpyrosAliv	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1093 ms	328 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n;
vector<int> a;

class Segtree {
    private:
    int n;
    vector<int> seg;
    void update(int node, int l, int r, int idx) {
        if (l == r) seg[node] = 1;
        else {
            int mid = (l + r) / 2;
            if (idx <= mid) update(node*2+1, l, mid, idx);
            else update(node*2+2, mid+1, r, idx);
            seg[node] = seg[node*2 + 1] + seg[node*2 + 2]; 
        }
    }
    int query(int node, int start, int end, int l, int r) {
        if (start > r || end < l) return 0;
        else if (start >= l && end <= r) return seg[node];
        else {
            int mid = (start + end) / 2;
            return query(node*2+1, start, mid, l, r) + query(node*2+2, mid+1, end, l, r);
        }
    }
    public:
    Segtree(int nn) {
        n = nn;
        seg.assign(n*4, 0);
    }
    void update(int idx) {
        update(0, 0, n-1, idx);
    }
    int query(int l, int r) {
        if (l > r) return 0;
        return query(0, 0, n-1, l, r);
    }
};

ll count_swaps(vector<int> s) {
    n = s.size();
    a = s;
    int c = 0;
    vector<int> r(n/2, 0), l(n/2, 0);
    for (int i = 1; i <= n/2; i++) {
        vector<int> L, R;
        for (int j = 0; j < n; j++) {
            if (abs(s[j]) != i) continue;
            if (s[j] < 0) L.push_back(j);
            else R.push_back(j);
        }
        int sz = L.size();
        for (int j = 0; j < sz; j++) {
            l[c] = L[j];
            r[c] = R[j];
            c++;
        }
    }
    n /= 2;
    vector<int> ord;
    for (int i = 0; i < n; i++) ord.push_back(i);
    ll ans = n*n*4;
    do {
        Segtree seg(n*2);
        ll curr = 0;
        int pos = 0;
        for (int i = 0; i < n; i++) {
            int p = l[i];
            int p2 = p + seg.query(p+1, n*2);
            curr += abs(p2 - pos);
            seg.update(p);
            pos++;
            p = r[i];
            p2 = p + seg.query(p+1, n*2);
            curr += abs(p2 - pos);
            seg.update(p);
            pos++;
        }
        ans = min(ans, curr);
    } while (next_permutation(ord.begin(), ord.end()));
    return ans;
}
/*
int main() {
    int n; cin >> n;
    vector<int> arr;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        arr.push_back(x);
    }
    cout << count_swaps(arr) << "\n";
}*/

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