제출 #1112755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112755		StefanSebez	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	63 ms	20200 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=2e5+50,inf=1e9;
ll res;
vector<int>vals[N],vals1[N];
int idx[N];
bool active[N];
int T[N+50];
void Update(int i,int x){for(i++;i<=N;i+=i&-i)T[i]+=x;}
int Get(int i){int x=0;for(i++;i>=1;i-=i&-i)x+=T[i];return x;}
long long count_swaps(std::vector<int> S){
	int n=S.size()/2;
	for(int i=0;i<2*n;i++){
		if(S[i]>0) vals[S[i]].pb(i);
		else vals1[-S[i]].pb(i);
		Update(i,1);
		active[i]=true;
	}
	for(int i=0;i<2*n;i++){
		if(!active[i]) continue;
		//printf("%i %lld\n",i,res);
		int k=abs(S[i]);
		//printf(" %i %i\n",vals[k][idx[k]],vals1[k][idx[k]]);
		Update(vals[k][idx[k]],-1);
		Update(vals1[k][idx[k]],-1);
		active[vals[k][idx[k]]]=active[vals1[k][idx[k]]]=false;
		res+=Get(max(vals[k][idx[k]],vals1[k][idx[k]]));
		if(vals1[k][idx[k]]>vals[k][idx[k]]) res++;
		idx[k]++;
	}
	/*for(int i=0;i<2*n;i+=2){
		for(int j=i+1;j<2*n;j++){
			if(S[i]==-S[j]){
				for(;j>i+1;j--){
					swap(S[j],S[j-1]);
					res++;
				}
				if(S[i]>S[i+1]) swap(S[i],S[i+1]),res++;
				break;
			}
		}
	}*/
	/*while(1){
		for(int i=0;i<2*n;i++) skip[i]=false;
		int l=-1,r=-1,mn=inf;
		for(int i=0;i<2*n;i++){
			if(skip[i]) continue;
			for(int j=i+1;j<2*n;j++){
				if(S[i]==-S[j]){
					int x=j-i-1;
					if(S[i]>0) x++;
					if(x==0){
						skip[i]=skip[i+1]=true;
						break;
					}
					if(mn>x){
						mn=x;
						l=i,r=j;
					}
				}
			}
		}
		//printf("%i %i\n",l,r);
		if(mn==inf) break;
		res+=mn;
		for(int i=r;i>l+1;i--){
			swap(S[i],S[i-1]);
		}
		if(S[l]>S[l+1]) swap(S[l],S[l+1]);
		//for(int i=0;i<2*n;i++) printf("%i ",S[i]);printf("\n");
	}*/
	return res;
}

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