Submission #145970

#	Time	Username	Problem	Language	Result	Execution time	Memory
145970		dennisstar	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	250 ms	140912 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
//c1:-, c2:+
deque<int> c1[100010], c2[100010];
int pi[200010];
int ar[600010]; const int MAX=(1<<18);
long long count_swaps(std::vector<int> s) {
	int i, j;
	int cnt=0;
	for (i=0; i<s.size(); i++) {
		if (s[i]>0) {
			if (c1[s[i]].empty()) c2[s[i]].push_back(i);
			else {
				pi[c1[s[i]].front()]=i;
				pi[i]=c1[s[i]].front();
				c1[s[i]].front()=-1;
				c1[s[i]].pop_front();
				cnt++;
			}
		}
		else if (s[i]<0) {
			if (c2[-s[i]].empty()) c1[-s[i]].push_back(i);
			else {
				pi[c2[-s[i]].front()]=i;
				pi[i]=c2[-s[i]].front();
				c2[-s[i]].front()=-1;
				c2[-s[i]].pop_front();
				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:12:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=0; i<s.size(); i++) {
            ~^~~~~~~~~
shoes.cpp:33:22: warning: division by zero [-Wdiv-by-zero]
   else printf("%d", 1/0);
                     ~^~
shoes.cpp:35:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (cnt<s.size()/2) {
      ~~~^~~~~~~~~~~
shoes.cpp:36:17: warning: division by zero [-Wdiv-by-zero]
   printf("%d", 1/0);
                ~^~
shoes.cpp:39:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=0; i<s.size(); i++) ar[MAX+i]=1;
            ~^~~~~~~~~
shoes.cpp:42:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (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