제출 #1255230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255230		nerrrmin	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	43 ms	8188 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const long long maxn = 2e5 + 10;
long long a[maxn], n;
long long merge_sort(long long l, long long r)
{
    if(l == r)return 0;
    long long mid = (l + r)/2;
    long long onleft = merge_sort(l, mid);
    long long onright = merge_sort(mid+1, r);
    long long ans = onleft + onright;
     long long i = l, j = mid+1;
     vector < long long > w;
     while(i <= mid && j <= r)
     {
         if(a[i] < a[j])
         {
             w.pb(a[i]);
             i ++;
         }
         else
         {
             w.pb(a[j]);
             j ++;
             ans += (mid - i + 1);
         }
     }
     while(i <= mid)
     {
         w.pb(a[i]);
         i ++;
     }
     while(j <= r)
     {
         w.pb(a[j]);
         j ++;
     }
     long long p = 0;
     for (long long i = l; i <= r; ++ i)
     {
         a[i] = w[p];
         p ++;
     }
     return ans;
}
long long count_swaps(std::vector< int > s)
{

    vector < long long > lt, rt;
    long long i = 1;
    for (auto x: s)
    {
        if(x < 0)lt.pb(i);
        else rt.pb(i);
        i ++;
    }
    n = s.size();
    long long pos = 1;
    for (long long i = 0; i < lt.size(); ++ i)
    {
        long long f = lt[i];
        long long s = rt[i];

       // cout << f << " " << s << endl;
        a[f] = pos;
        pos ++;
        a[s] = pos;
        pos ++;
    }

 //   for (long long i = 1; i <= n; ++ i)
//        cout << a[i] << " ";
 //   cout << endl;
    return merge_sort(1, n);
}

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