Submission #601822

#	Time	Username	Problem	Language	Result	Execution time	Memory
601822		chirathnirodha	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	105 ms	17392 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long ll;

int seg[800000];
void update(ll a,ll b,ll c,ll x,ll y){
	if(x<=a && b<=y){seg[c]++;return;}
	ll m=(a+b)/2;
	if(y<=m)update(a,m,2*c,x,y);
	else if(x>=m+1)update(m+1,b,2*c+1,x,y);
	else {
		update(a,m,2*c,x,m);
		update(m+1,b,2*c+1,m+1,y);
	}
}
int findseg(ll a,ll b,ll c,ll x){
	if(a==x && b==x)return seg[c];
	ll m=(a+b)/2;
	if(x<=m)return seg[c]+findseg(a,m,2*c,x);
	else return seg[c]+findseg(m+1,b,2*c+1,x);
}
long long count_swaps(vector<int> s){
	ll ans=0;
	int n=s.size()/2;
	memset(seg,0,sizeof(seg));
	vector<int> pos[n+1],neg[n+1];
    bool visited[2*n];memset(visited,false,sizeof(visited));
	for(int i=2*n-1;i>=0;i--){
		if(s[i]>0)pos[s[i]].PB(i);
		else neg[-s[i]].PB(i);
	}
	for(int i=0;i<2*n;i++){
		int ind=-1;
        if(visited[i]==true)continue;
		if(s[i]>0){
            pos[s[i]].pop_back();
            while(!neg[s[i]].empty()){
                ind=neg[s[i]].back();
			    neg[s[i]].pop_back();
                if(visited[ind]==false)break;
            }
			ans++;
		}
		else{
            neg[-s[i]].pop_back();
            while(!pos[-s[i]].empty()){
                ind=pos[-s[i]].back();
			    pos[-s[i]].pop_back();
                if(visited[ind]==false)break;
            }
		}
        if(ind==-1)continue;
        visited[i]=visited[ind]=true;
        int incind=findseg(0,2*n-1,1,ind);
        int inci=findseg(0,2*n-1,1,i);
		ans+=(ind+incind)-(i+inci)-1;
		if(ind+incind>i+inci+1)update(0,2*n-1,1,i+1,ind-1);
	}
	return ans;
}

Compilation message (stderr)

In file included from /usr/include/string.h:495,
                 from /usr/include/c++/10/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
                 from shoes.cpp:2:
In function 'void* memset(void*, int, size_t)',
    inlined from 'long long int count_swaps(std::vector<int>)' at shoes.cpp:30:29:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:71:33: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing between 18446744071562067968 and 18446744073709551614 bytes into a region of size between 18446744071562067968 and 18446744073709551614 [-Wstringop-overflow=]
   71 |   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:30:10: note: at offset 0 to an object with size between 18446744071562067968 and 18446744073709551614 declared here
   30 |     bool visited[2*n];memset(visited,false,sizeof(visited));
      |          ^~~~~~~

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