Submission #1323958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323958		aritro_	Arranging Shoes (IOI19_shoes)	C++20	85 / 100	1095 ms	3240 KiB

shoes

//#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back

ll count_swaps(std::vector<int> a){
    int n=a.size();
    bool b=1;
    for(int i=0;i<n;i++) if(abs(a[0])!=abs(a[i])) b=0;
    bool b2=1;
    for(int i=0;i<(n/2);i++){
        if(a[i]>0) b2=0;
        if(a[i+(n/2)]!=abs(a[i])) b2=0;
    }
    if(b2||b){
        string s="";
        for(int i=0;i<n;i++){
            if(a[i]>0) s+='R';
            else s+='L';
        }
        //cout<<s<<endl;
        vector<ll> l;
        for(int i=0;i<n;i++) if(s[i]=='L') l.pb(i);
        ll ans=0;
        for(int i=0;i<(n/2);i++) ans+=abs(l[i]-(2*i)); 
        return ans;
    }

    ll l=0,r=0;
    ll ans=0;
    while(l<n){
 	    r++;
 	    int k=-1*a[l];
 	    if(k==a[r]){
 		    ans+=r-l-1;
 		    for(int i=r;i>l+1;i--) swap(a[i],a[i-1]);
 			if(a[l]>0){
 				ans++;
 				swap(a[l],a[l+1]);
 			}
 			l+=2;
 		    r=l;
 		}
 	}
 	return ans;
}

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