Submission #380828

#	Time	Username	Problem	Language	Result	Execution time	Memory
380828		Karliver	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1100 ms	21736 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#include <fstream>
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
typedef complex<ll> G;
const int INF = 1e9 + 1;
const int N = 1e6;
const double eps = 1e-3;

using namespace std;
struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

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

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }

};
long long count_swaps(std::vector<int> a) {
    int n = a.size();


    FenwickTree F(n);
    ll ans = 0;
    vector<vector<int>> le(n + 1), ri(n + 1);
    forn(i, n) {
        if(a[i] > 0)ri[a[i]].push_back(i);
        else
            le[-a[i]].push_back(i);
    }
    vector<int> flow;
    vector<int> cnt1(n + 1, 0), cnt2(n + 1, 0);
    forn(i, n) {
        if(a[i] > 0) {
            if(!cnt2[a[i]])flow.push_back(a[i]);
            else {
                --cnt2[a[i]];
                continue;
            }
            ++cnt1[a[i]];
        }
        else {
            if(!cnt1[-a[i]])flow.push_back(a[i]);
            else {
                --cnt1[-a[i]];
                continue;
            }
            cnt2[-a[i]]++;
        }
    }
    assert(flow.size() == n /2);
    for(int i = 0;i < n / 2;++i) {

        if(flow[i] < 0) {
            int now = le[-flow[i]][0];
            int f = -flow[i];
            assert(ri[f].size() && le[f].size());
            int tar = ri[f][0];
            assert(tar > now);
            ans += tar - now - F.sum(now) + F.sum(tar) - 1;
            F.add(now + 1, 1);
            F.add(tar, -1);
            le[f].erase(le[f].begin());
            ri[f].erase(ri[f].begin());
        }
        else {
            int now = ri[flow[i]][0];
            int f = flow[i];
            assert(ri[f].size() && le[f].size());
            int tar = le[f][0];
            assert(tar > now);

            ans += tar - now - F.sum(now) + F.sum(tar);
            F.add(now, 1);
            F.add(tar, -1);
            le[f].erase(le[f].begin());
            ri[f].erase(ri[f].begin());
        }

    }

    return ans;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from shoes.cpp:2:
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:81:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |     assert(flow.size() == n /2);
      |            ~~~~~~~~~~~~^~~~~~~

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