제출 #155638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
155638		Berted	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	357 ms	207072 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <deque>
#define ll long long
using namespace std;
bool skp[300021]={};
int fwk[300021]={},n,pr=0;
deque<int> v[300021]={};
ll rs = 0;
int qry(int x)
{
	x = n+1 - x;
	int to = 0;
	for (;x;x-=x&(-x)) {to+=fwk[x];}
	return to;
}
void upd(int x,int v)
{
	x = n+1 - x;
	for (;x<=n;x+=x&(-x)) {fwk[x]+=v;}
}
long long count_swaps(vector<int> s) 
{
	n = s.size();
	for (int i=0;i<s.size();i++) {v[s[i]+n].push_back(i+1);upd(i+1,i+1);upd(i,-i-1);}
	int i=0;
	while (pr<n)
	{
		while (skp[i]) {i++;}
		//cout<<i+1<<" "<<v[-s[i]+n].front()<<" "<<qry(v[-s[i]+n].front())<<" "<<qry(i+1)<<"\n";
		skp[v[-s[i]+n].front()-1] = 1;
		rs += (ll)qry(v[-s[i]+n].front()) - (ll)(qry(i+1)+(s[i]<0));
		upd(v[-s[i]+n].front(),1);
		v[s[i]+n].pop_front();
		v[-s[i]+n].pop_front();
		i++;
		pr += 2;
	}
	return rs;
}

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<s.size();i++) {v[s[i]+n].push_back(i+1);upd(i+1,i+1);upd(i,-i-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