Submission #331576

#	Time	Username	Problem	Language	Result	Execution time	Memory
331576		couplefire	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	206 ms	13548 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005

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;
    }
};
FenwickTree tree(MAXN);
vector<int> arr[MAXN];
map<int, int> mp;

long long count_swaps(vector<int> s) {
    long long ans = 0;
    int n = s.size();
    int cur = 0;
    for(int i = 0; i<n; i++){
        arr[abs(s[i])].push_back(s[i]);
        s[i] = abs(s[i]);
        if(mp.count(s[i])){
            s[i] = mp[s[i]];
        }
        else{
            mp[s[i]] = ++cur;
            s[i] = cur;
        }
    }
    for(int i = 1; i<=n/2; i++){
        long long tmp = 0;
        int shift = 0;
        queue<pair<int, int>> q;
        for(int j = 0; j<arr[i].size(); j++){
            if(q.empty() || q.front().first/arr[i][j] == 1){
                q.push({arr[i][j], j-shift});
            }
            else{
                tmp += j-shift-q.front().second-(q.front().first < 0);
                q.pop();
                shift++;
            }
        }
        ans += tmp;
    }
    for(int i = n-1; i>=0; i--){
        ans += tree.sum(0, s[i]-1);
        tree.add(s[i], 1);
    }
	return ans;
}

// int main() {
//     freopen("a.in", "r", stdin);
// 	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;
// }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:58:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int j = 0; j<arr[i].size(); j++){
      |                        ~^~~~~~~~~~~~~~

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