Submission #406033

#	Time	Username	Problem	Language	Result	Execution time	Memory
406033		ngrace	Arranging Shoes (IOI19_shoes)	C++14	65 / 100	33 ms	3108 KiB

shoes

#include "shoes.h"

long long count_swaps(std::vector<int> s) {
	int n=s.size()/2;
	if(n<=1000){//sub 1, 2 and 5
		long long out=0;
		for(int i=0;i<n*2;i+=2){
			int cur=s[i];
			int ind=i+1;
			while(s[ind]!=-cur) ind++;
			
			while(ind>i+1){
				int tmp=s[ind];
				s[ind]=s[ind-1];
				s[ind-1]=tmp;
				ind--;
				out++;
			}
			if(s[i]>s[i+1]){
				out++;
			}
		}
		return out;
	}
	else{
		//assume sub 4
		long long out=0;
		for(int i=0;i<s.size()/2;i++){
			out+=i;
		}
		return out;
	}
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:28:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i=0;i<s.size()/2;i++){
      |               ~^~~~~~~~~~~

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