Submission #145960

#	Time	Username	Problem	Language	Result	Execution time	Memory
145960		dennisstar	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	3 ms	1016 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<=s.size(); i++) {
		c1[i]=-1;
		c2[i]=-1;
	}
	int cnt=0;
	for (i=0; i<s.size(); i++) {
		if (s[i]>0) {
			if (c1[s[i]]==-1) {c2[s[i]]=i;}
			else {
				pi[c1[s[i]]]=i;
				pi[i]=c1[s[i]];
				c1[s[i]]=-1;
				cnt++;
			}
		}
		else if (s[i]<0) {
			if (c2[-s[i]]==-1) {c1[-s[i]]=i;}
			else {
				pi[c2[-s[i]]]=i;
				pi[i]=c2[-s[i]];
				c2[-s[i]]=-1;
				cnt++;
			}
		}
		else printf("%d", 1/0);
	}
	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:10:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=0; i<=s.size(); i++) {
            ~^~~~~~~~~~
shoes.cpp:15:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=0; i<s.size(); i++) {
            ~^~~~~~~~~
shoes.cpp:34:22: warning: division by zero [-Wdiv-by-zero]
   else printf("%d", 1/0);
                     ~^~
shoes.cpp:36:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (cnt<s.size()/2) {
      ~~~^~~~~~~~~~~
shoes.cpp:37:17: warning: division by zero [-Wdiv-by-zero]
   printf("%d", 1/0);
                ~^~
shoes.cpp:40:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=0; i<s.size(); i++) ar[MAX+i]=1;
            ~^~~~~~~~~
shoes.cpp:43: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