Submission #799123

#	Time	Username	Problem	Language	Result	Execution time	Memory
799123		I_Love_EliskaM_	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	477 ms	148716 KiB

shoes

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

struct BIT {
    vector<int> bit;  // binary indexed tree
    int n;
 
    BIT(int n) {
        this->n = n;
        bit.assign(n, 0);
    }
 
    BIT(vector<int> a) : BIT(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;
    }
};

ll count_swaps(vector<int>s) {

	int n=s.size()/2;
	/*
	if (n==1) {
		return s[0]>0;
	}
	int foo=1; int x=abs(s[0]);
	for (int i=1; i<2*n; ++i) {
		foo&=abs(s[i])==x;
	}
	if (foo) {
		int j=0;
		ll ans=0;
		for (int i=0; i<2*n; ++i) {
			if (s[i]<0) {
				ans+=abs(i-2*j);
				++j;
			}
		}
		return ans;
	}
	foo=1;
	for (int i=0; i<n; ++i) {
		foo&= ( s[i]<0 && (abs(s[i])==abs(s[i+n])) && s[i+n]>0 );
	}
	if (foo) {
		return 1ll*n*(n-1)/2;
	} */

	ll ans=0;

	BIT ft(2*n+10);
	for (int i=0; i<2*n; ++i) { ft.add(i,i); ft.add(i+1,-i); }
	vector<int> vis(2*n,0);
	
	//for (int i=0; i<2*n; ++i) cout<<ft.sum(0,i)<<' '; cout<<'\n';
	
	map<int,queue<int>> m;
	for (int i=0; i<2*n; ++i) m[s[i]].push(i);
	for (int i=0; i<2*n; ++i) {
		if (vis[i]) continue;
		vis[i]=1;
		int x=s[i];
		m[x].pop();
		int j=m[-x].front();
		m[-x].pop();
		int y=ft.sum(0,i);
		int z=ft.sum(0,j);
		ans+=z-y-1;
		ans+=s[i]>0;
		vis[j]=1;

		//cout<<i<<' '<<j<<' '<<y<<' '<<z<<' '<<ans<<'\n';

		ft.add(i,1);
		ft.add(j,-1);
		//for (int i=0; i<2*n; ++i) cout<<ft.sum(0,i)<<' '; cout<<'\n';
	}

	return ans;	
}

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