Submission #145958

#	Time	Username	Problem	Language	Result	Execution time	Memory
145958		dennisstar	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	7 ms	3704 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;
	int cnt=0;
	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;
				cnt++;
			}
			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;
				cnt++;
			}
			else c1[-s[i]]=i;
		}
	}
	if (cnt!=s.size()/2) {
		printf("%d", 1/0);
		return 0;
	}
	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:12:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=0; i<s.size(); i++) {
            ~^~~~~~~~~
shoes.cpp:32:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (cnt!=s.size()/2) {
      ~~~^~~~~~~~~~~~
shoes.cpp:33:17: warning: division by zero [-Wdiv-by-zero]
   printf("%d", 1/0);
                ~^~
shoes.cpp:36:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=0; i<s.size(); i++) ar[MAX+i]=1;
            ~^~~~~~~~~
shoes.cpp:39: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