Submission #211179

#	Time	Username	Problem	Language	Result	Execution time	Memory
211179		lyh	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	232 ms	140408 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn= 2e5 + 10;
const int n= 1e5 + 1;
bool vis[maxn];
queue< int > q[maxn];
long long bit[maxn];
vector< int > v;
int lowbit(int a) {
	return a & (-a);
}
void modify(int a, int x) {
	while(a <= maxn) {
		bit[a]+= x;
		a+= lowbit(a);
	}
}
long long query(int a) {
	long long res= 0;
	while(a > 0) {
		res+= bit[a];
		a-= lowbit(a);
	}
	return res;
}
long long count_swaps(std::vector< int > s) {
	long long tot= 0;
	for(int i= 0; i < s.size(); i++) {
		q[s[i] + n].push(i + 1);
		modify(i + 1, 1);
	}
	for(int i= 0; i < s.size(); i++) {
		if(vis[i + 1]) continue;
		int cnt= s[i];
		int y= q[-s[i] + n].front();
		q[s[i] + n].pop();
		q[-s[i] + n].pop();
		tot+= query(y - 1) - query(i + 1);
		modify(i + 1, -1);
		modify(y, -1);
		vis[i + 1]= 1;
		vis[y]= 1;
		if(cnt > 0) tot++;
	}
	return tot;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i= 0; i < s.size(); i++) {
                ~~^~~~~~~~~~
shoes.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i= 0; i < s.size(); i++) {
                ~~^~~~~~~~~~

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