Submission #143730

#	Time	Username	Problem	Language	Result	Execution time	Memory
143730		guangxuan	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	283 ms	138488 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define VPII vector<pair<int,int> >
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL MOD = 1e9+7;
const int SIZE = 1e6+5;
const LL INF = 1LL<<58;
const double eps = 1e-10;

int fw[200009];

void up(int x,int v){
	x+=2;
	for(;x<200009;x+=x&(-x))fw[x]+=v;
}

int qu(int x){
	x+=2;
	int ans=0;
	for(;x;x-=x&(-x))ans+=fw[x];
	return ans;
}
queue<int> pos[200009];//shoes of each type!
int N,H;
bool taken[200009];

long long count_swaps(std::vector<int> s) {
	N=SZ(s);
	H=N/2;
	REP(i,N){
		if(s[i]<0)s[i]=-s[i];
		else s[i]=H+s[i];
		pos[s[i]].push(i);
		up(i+1,1); //fw parameters are 0 indexed!!
	}
	long long ans =0;
	REP(i,N){
		if(taken[i])continue;
		int mi;//matching index
		if(s[i]<=H){//left shoe
			mi=s[i]+H;
		}
		else{
			mi=s[i]-H;
		}
		int mpos = pos[mi].front();//matching position
		ans += qu(mpos)-qu(i)-(s[i]<=H);//find position of mpos
		//printf("ans: %lld\n",ans);
		up(i+1,1);up(mpos,-1);
		taken[mpos]=taken[i]=1;
		pos[mi].pop();
		pos[s[i]].pop();
	}
	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