Submission #378995

#	Time	Username	Problem	Language	Result	Execution time	Memory
378995		Thistle	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	152 ms	75328 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){
		if(r<=l) return 0;
		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<H>>cnt(n+1);
	//moshi mada amatteiru nara
	//sokomade tobashimasu
	BIT bit(2*n);
	rep(i,2*n) bit.add(i,1);
	ll ans=0;
	rep(i,2*n){
		int t=abs(s[i]);
		int k=0;
		if(s[i]>0) k=1;
		if(cnt[t].empty()){
			cnt[t].push(H{i,k});
			continue;
		}
		if(cnt[t].front().sc==k){
			cnt[t].push(H{i,k});
		}
		else{
			int r=cnt[t].front().fs;
			cnt[t].pop();
			ans+=bit.query(r+1,i);
			bit.add(i,-1);
			bit.add(r,1);
			if(k==0) ans++;
		}
	}
	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:53:2: note: in expansion of macro 'rep'
   53 |  rep(i,2*n) bit.add(i,1);
      |  ^~~
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:55:2: note: in expansion of macro 'rep'
   55 |  rep(i,2*n){
      |  ^~~
shoes.cpp:48:6: warning: unused variable 'tmp' [-Wunused-variable]
   48 |  int tmp=0;
      |      ^~~

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