Submission #605773

#	Time	Username	Problem	Language	Result	Execution time	Memory
605773		rrrr10000	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	147 ms	22708 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define fi first
#define se second
#define pb emplace_back
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
const ll inf=1001001001;

struct BIT{
	vi bit;
	ll n;
	BIT(ll n_):n(n_),bit(n_+1){}
	void add(ll i,ll x){
		for(i++;i<=n;i+=i&-i)bit[i]+=x;
	}
	ll sum(ll i){
		ll res=0;
		for(;i>0;i-=i&-i)res+=bit[i];
		return res;
	}
	ll get(ll l,ll r){
		return sum(r)-sum(l);
	}
};
long long count_swaps(std::vector<int> s) {
	ll n=s.size(),ans=0;
	vvvi al(n/2,vvi(2));
	vp v(n);
	rep(i,n)v[i]=P(abs(s[i])-1,(int)(s[i]<0));
	for(int i=n-1;i>=0;i--)al[v[i].fi][v[i].se].pb(i);
	vb done(n,false);
	BIT bit(n);
	rep(i,n)bit.add(i,1);
	rep(i,n)if(!done[i]){
		ans+=bit.get(i,al[v[i].fi][v[i].se^1].back())-v[i].se;
		rep(j,2){
			done[al[v[i].fi][j].back()]=true;
			bit.add(al[v[i].fi][j].back(),-1);
			al[v[i].fi][j].pop_back();
		}
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In constructor 'BIT::BIT(ll)':
shoes.cpp:28:5: warning: 'BIT::n' will be initialized after [-Wreorder]
   28 |  ll n;
      |     ^
shoes.cpp:27:5: warning:   'vi BIT::bit' [-Wreorder]
   27 |  vi bit;
      |     ^~~
shoes.cpp:29:2: warning:   when initialized here [-Wreorder]
   29 |  BIT(ll n_):n(n_),bit(n_+1){}
      |  ^~~

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