Submission #1322374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322374		ElayV13	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	0 ms	332 KiB

shoes

#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;

#define ll long long

ll get(vector<int>p,vector<int>s)
{
   vector<int>need;
   for(int i=0;i<p.size();i++)
   {
      need.push_back(-p[i]);
      need.push_back(p[i]);
   }
   int n=(int)s.size();
   vector<bool>used(n,false);
   long long res=0;
   for(int i=0;i<need.size();i++)
   {
      if(need[i]>0) continue;
      long long f=-1,si=-1;
      for(int j=0;j<n;j++)
      {
         if(used[j]) continue;
         if(s[j]==abs(need[i])&&f==-1){
            f=j;
            break;
         }
      }
      used[f]=1;
      for(int j=0;j<n;j++)
      {
         if(used[j]) continue;
         if(s[j]==need[i]&&si==-1){
            si=j;
            break;
         }
      }
      used[si]=1;
      int add=max(0ll,f-i)+max(0ll,si-i);
      if(!add&&(f<si)) ++add;
      res+=add;
   }
   return res;
}

ll count_swaps(vector<int>s)
{
   int n=(int)s.size();
   vector<int>p;
   for(int i=0;i<n;i++)
   {
      if(s[i]>0) p.push_back(s[i]);
   }
   sort(p.begin(),p.end());
   ll res=get(p,s);
   while(next_permutation(p.begin(),p.end())) res=min(res,get(p,s));
   return res;
}

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