Submission #891432

#	Time	Username	Problem	Language	Result	Execution time	Memory
891432		Muhammad_Aneeq	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	38 ms	8068 KiB

shoes

#include <set>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
vector<long long>a;
long long n;
long long solve1()
{
  vector<long long>neg,pos;
  for (long long i=0;i<2*n;i++)
  {
    if (a[i]>0)
      pos.push_back(i);
    else
      neg.push_back(i);
  }
  reverse(begin(pos),end(pos));
  reverse(begin(neg),end(neg));
  vector<long long>curp,curn;
  long long ans=0;
  for (long long i=0;i<2*n;i++)
  {
    if (i%2==0)
    {
      long long z=lower_bound(begin(curp),end(curp),neg.back())-begin(curp);
      long long u=lower_bound(begin(curn),end(curn),neg.back())-begin(curn);
      ans+=abs((long long)(neg.back()-z-u));
      curp.push_back(neg.back());
      neg.pop_back();
    }
    else
    {
      long long z=lower_bound(begin(curp),end(curp),pos.back())-begin(curp);
      long long u=lower_bound(begin(curn),end(curn),pos.back())-begin(curn);
      ans+=abs((long long)(pos.back()-z-u));
      curn.push_back(pos.back());
      pos.pop_back();
    }
  }
  return ans;
}
long long count_swaps(vector<int>s)
{
  set<long long>g;
  n=s.size()/2;
  a={begin(s),end(s)};
  for (auto i:s)
  {
    if (i>0)
      g.insert(i);
  }
  if (g.size()==1)
    return solve1();
  bool w=0;
  for (long long i=0;i<n;i++)
  {
    if (s[i]!=-s[i+n])
      w=1;
  }
  if (w==0)
  {
    return (n*(n-1))/2;
  } 
  map<long long,long long>d;
  for (long long i=0;i<2*n;i++)
    d[a[i]]=i;
  vector<long long>x={begin(g),end(g)};
  long long ans=1e15+10;
  do
  {
    vector<long long>cur;
    long long f=0;
    for (long long i=0;i<n;i++)
    {
      long long z=lower_bound(begin(cur),end(cur),d[-x[i]])-begin(cur);
      f+=abs((long long)(d[-x[i]]+cur.size()-z-2*i));
      cur.push_back(d[-x[i]]);
      sort(begin(cur),end(cur));
      z=lower_bound(begin(cur),end(cur),d[x[i]])-begin(cur);
      f+=abs((long long)(d[x[i]]+cur.size()-z-2*i-1));
      cur.push_back(d[x[i]]);
      sort(begin(cur),end(cur));
    }
    ans=min(ans,f);
  }
  while (next_permutation(begin(x),end(x)));
  return ans;
}

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