Submission #959451

#	Time	Username	Problem	Language	Result	Execution time	Memory
959451		NemanjaSo2005	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1082 ms	148952 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
ll N,niz[maxn],par[maxn];
ll res=0;
map<int,queue<int>> mapa;
ll count_swaps(vector<int> s) {
	N=s.size();
	for(int i=0;i<N;i++)
      niz[i+1]=s[i];
   for(int i=1;i<=N;i++){
      int sup=-niz[i];
      if(mapa[sup].size()!=0){
         int x=mapa[sup].front();
         mapa[sup].pop();
         par[x]=i;
         par[i]=x;
         continue;
      }
      mapa[niz[i]].push(i);
   }
   for(int i=1;i<=N;i++){
      if(niz[i]==0)
         continue;
      if(niz[i]>0) /// Zamena leva-desna na kraju
         res++;
      for(int j=i+1;j<par[i];j++)
         if(niz[j]!=0)
            res++;
      niz[i]=0;
      niz[par[i]]=0;
   }
   return res;
}

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