Submission #145950

#	Time	Username	Problem	Language	Result	Execution time	Memory
145950		dennisstar	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	58 ms	6028 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int c1[200010], c2[200010]; //c1:-, c2:+
int pi[200010];
int ar[600010]; const int MAX=(1<<18);
long long count_swaps(std::vector<int> s) {
	int i, j;
	for (i=0; i<200000; i++) c1[i]=c2[i]=-1;
	for (i=0; i<s.size(); i++) {
		if (s[i]>0) {
			if (c1[s[i]]>=0) {
				pi[c1[s[i]]]=i;
				pi[i]=c1[s[i]];
				c1[s[i]]=-1;
			}
			else c2[s[i]]=i;
		}
		else {
			if (c2[-s[i]]>=0) {
				pi[c2[-s[i]]]=i;
				pi[i]=c2[-s[i]];
				c2[-s[i]]=-1;
			}
			else c1[-s[i]]=i;
		}
	}
	for (i=0; i<s.size(); i++) ar[MAX+i]=1;
	for (i=MAX+s.size()-1; i; i--) ar[i/2]+=ar[i];
	ll ans=0; int fr, re;
	for (i=0; i<s.size(); i++) {
		if (!ar[MAX+i]) continue;
		if (s[i]>0) ans++;
		fr=i+1+MAX, re=pi[i]-1+MAX;
		while (fr<=re) {
			if (fr&1) ans+=(ll)ar[fr++];
			if (!(re&1)) ans+=(ll)ar[re--];
			fr/=2; re/=2;
		}
		for (j=i+MAX; j; j/=2) ar[j]--;
		for (j=pi[i]+MAX; j; j/=2) ar[j]--;
	}
	return ans;
}

Compilation message (stderr)

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

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