Submission #331575

#	Time	Username	Problem	Language	Result	Execution time	Memory
331575		couplefire	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 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++){
      |                        ~^~~~~~~~~~~~~~
shoes.cpp: In function 'int main()':
shoes.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   78 |     freopen("a.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
/tmp/ccmOSMpC.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccLgzQN5.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status