Submission #387488

#	Time	Username	Problem	Language	Result	Execution time	Memory
387488		kimbj0709	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	230 ms	24524 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
long long int ans = 0;
vector<int> merge_sort(vector<int> vect1){
  if(vect1.size()<=1){
    return vect1;
  }
  vector<int> left,right;
  for(int i=0;i<vect1.size()/2;i++){
    left.push_back(vect1[i]);
  }
  for(int i=vect1.size()/2;i<vect1.size();i++){
    right.push_back(vect1[i]);
  }
  left = merge_sort(left);
  right = merge_sort(right);
  vector<int> curr;
  left.push_back(INT_MAX);
  right.push_back(INT_MAX);
  reverse(left.begin(),left.end());
  reverse(right.begin(),right.end());
  for(int i=0;i<vect1.size();i++){
    if(left.back()<right.back()){
      curr.push_back(left.back());
      left.pop_back();
    }
    else{
      ans += left.size()-1;
      curr.push_back(right.back());
      right.pop_back();
    }
  }
  return curr;
}
long long count_swaps(std::vector<int> s) {
  int n = s.size();
  vector<vector<int> > nexts(s.size()*2+100);
  for(int i=0;i<s.size();i++){
    if(s[i]>0){
      nexts[s[i]].push_back(i);
    }
    else{
      nexts[s[i]*(-1)+n].push_back(i);
    }
  }
  for(int i=0;i<nexts.size();i++){
    reverse(nexts[i].begin(),nexts[i].end());
  }
  vector<int> treated(s.size(),0);
  int currpos = 0;
  vector<int> positions(n,-1);
  for(int i=0;i<n;i++){
    if(treated[i]==1){
      continue;
    }
    if(s[i]<0){
      positions[i] = currpos;
      positions[nexts[s[i]*-1].back()] = currpos+1;
      treated[nexts[s[i]*-1].back()] = 1;
      nexts[s[i]*-1+n].pop_back();
      nexts[s[i]*-1].pop_back();
    }
    else{
      positions[i] = currpos+1;
      positions[nexts[s[i]+n].back()] = currpos;
      treated[nexts[s[i]+n].back()] = 1;
      nexts[s[i]+n].pop_back();
      nexts[s[i]].pop_back();
    }
    currpos += 2;
  }
  merge_sort(positions);
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'std::vector<int> merge_sort(std::vector<int>)':
shoes.cpp:10:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |   for(int i=0;i<vect1.size()/2;i++){
      |               ~^~~~~~~~~~~~~~~
shoes.cpp:13:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   for(int i=vect1.size()/2;i<vect1.size();i++){
      |                            ~^~~~~~~~~~~~~
shoes.cpp:23:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int i=0;i<vect1.size();i++){
      |               ~^~~~~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int i=0;i<s.size();i++){
      |               ~^~~~~~~~~
shoes.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0;i<nexts.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