Submission #378787

#	Time	Username	Problem	Language	Result	Execution time	Memory
378787		Thistle	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	123 ms	74604 KiB

shoes

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

using ll=long long;
using H=pair<ll, ll>;
using vi=vector<ll>;
#define vec vector
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),(0),(n))
#define fs first
#define sc second
#define all(a) (a).begin(),(a).end()
#define siz(a) ll((a).size())

class BIT{
	int n;
	vi dat;
public:
	BIT(int n):n(n){
		dat.assign(n+1,0);
	}
	void add(int t,ll x){
		t++;
		while(t<=n){
			dat[t]+=x;
			t+=t&-t;
		}
	}
	ll query(int x){
		x++;
		ll ret=0;
		while(x>0){
			ret+=dat[x];
			x-=x&-x;
		}
		return ret;
	}
	ll query(int l,int r){
		return query(r-1)-query(l-1);
	}
};

long long count_swaps(std::vector<int> s) {
	int n=siz(s)/2;
	vi v(2*n);
	int tmp=0;
	vec<queue<ll>>cnt(n+1);
	rep(i,2*n){
		if(s[i]<0){
			v[i]=tmp;
			cnt[-s[i]].push(tmp+1);
			tmp+=2;
		}
	}
	rep(i,2*n){
		if(s[i]>0){
			v[i]=cnt[s[i]].front();
			cnt[s[i]].pop();
		}
	}
	ll ans=0;
	BIT bit(2*n);
	rep(i,2*n){
		ans+=bit.query(v[i]+1,2*n);
		bit.add(v[i],1);
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
shoes.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
shoes.cpp:49:2: note: in expansion of macro 'rep'
   49 |  rep(i,2*n){
      |  ^~~
shoes.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
shoes.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
shoes.cpp:56:2: note: in expansion of macro 'rep'
   56 |  rep(i,2*n){
      |  ^~~
shoes.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
shoes.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
shoes.cpp:64:2: note: in expansion of macro 'rep'
   64 |  rep(i,2*n){
      |  ^~~

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