Submission #426915

#	Time	Username	Problem	Language	Result	Execution time	Memory
426915		APROHACK	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	1 ms	332 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PB push_back
struct segtree{
	long long dd, htt, mid, val;
	segtree *L, *R;
	segtree(int l, int r){
		//cout<<l<<" "<<r<<endl;
		htt=r;
		dd=l;
		val=0;
		mid=(htt+dd)/2;
		if(l!=r){
			L=new segtree(l, mid);
			R=new segtree(mid+1, r);
			val=L->val+R->val;
		}else{
			val=1;
		}
		
	}
	void update(int ps){
		
		if(dd==htt){
			val=0;
			cout<<ps<<endl;
			return ;
		}
		if(ps<=mid){
			L->update(ps);
		}else{
			R->update(ps);
		}
		val=L->val+R->val;
	}
	long long query(int l, int r){
		if(dd==l&&r==htt){
			return val;
		}
		else if(r<=mid)return L->query(l, r);
		else if(l>mid)return R->query(l, r);
		else return L->query(l, mid)+R->query(mid+1, r);
	}

};
long long count_swaps(std::vector<int> s) {
	long long n = s.size()/2, sum=0;
	/*
	for(int i = 0 ; i < n ; i++){
		sum+=i;
	}*/
	vector<int>pos[n*2+1];
	int conut[n*2+1];
	memset(conut, -1, sizeof conut);
	//bool contado[n*2+1];
	for(int i = 0 ; i < n * 2 ; i++){
		//contado[abs(s[i])*2]=false;
		if(s[i]>0){//par
			pos[s[i]*2].PB(i);
			if(conut[s[i]*2]==-1)conut[s[i]*2]=i;
		}else{
			pos[(-s[i]*2)-1].PB(i);
			if(conut[s[i]*2-1]==-1)conut[(-s[i]*2)-1]=i;
		}
	}
	segtree *tree = new segtree(0, n*2);
	for(int i = 0 ; i < n*2 ; i++){
		if(s[i]>0){
			conut[s[i]*2]++;
			s[conut[s[i]*2-1]]=0;
			tree->update(conut[s[i]*2-1]);
			sum+=tree->query(i, conut[s[i]*2-1])-1;
			conut[s[i]*2-1]++;
		}else if(s[i]<0){
			conut[s[i]*2-1]++;
			s[conut[s[i]*2]]=0;
			tree->update(conut[s[i]*2]);
			sum+=tree->query(i+1, conut[s[i]*2])-1;
			conut[s[i]*2]++;
		}
	}

	return sum;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:77:18: warning: array subscript -3 is below array bounds of 'int [(<anonymous> + 1)]' [-Warray-bounds]
   77 |    conut[s[i]*2-1]++;
      |    ~~~~~~~~~~~~~~^
shoes.cpp:77:18: warning: array subscript -3 is below array bounds of 'int [(<anonymous> + 1)]' [-Warray-bounds]

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