Submission #1199001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199001		n3rm1n	Sorting (IOI15_sorting)	C++20	20 / 100	2 ms	2884 KiB

sorting

#include<bits/stdc++.h>
#define pb push_back
#include "sorting.h"
using namespace std;
const int maxn = 1e5 + 10;
int n, m;
int s[maxn];
int a[maxn];
int sx[maxn], sy[maxn];
vector < int > g[maxn];
int used[maxn];

void dfs(int beg)
{
    used[beg] = 1;
    for (auto nb: g[beg])
        if(!used[nb])dfs(nb);
}
bool check(int x)
{
    for (int i = 0; i < n; ++ i)
    {
        a[i] = s[i];
        g[i].clear();
        used[i] = 0;
    }
    for (int i = 0; i < x; ++ i)
        swap(a[sx[i]],a[sy[i]]);
    int cnt_cycles = 0;

    for (int i = 0; i < n; ++ i)
    {
        if(a[i] != i)g[a[i]].pb(i);
        else
        {
            used[i] = 1;
            cnt_cycles ++;
        }
    }
    for (int i = 0; i < n; ++ i)
    {
        if(used[i])continue;
        cnt_cycles ++;
        dfs(i);
    }
    return (n - cnt_cycles <= x);
}

int val[maxn], pos[maxn];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    n = N;
    m = M;
    int is = 1;
    for (int i = 0; i < n; ++ i)
    {
        s[i] = S[i];
        if(i != s[i])is = 0;
    }
    if(is)return 0;
    for (int i = 0; i < m; ++ i)
    {
        sx[i] = X[i];
        sy[i] = Y[i];
    }
    int l = 1, r = m, mid, res = m;
    while(l <= r)
    {
        mid = (l + r)/2;
        if(check(mid))
        {
            res = mid;
           r = mid - 1;
        }
        else l = mid + 1;
    }
    for (int i = 0; i < n; ++ i)
        val[i] = i;

    check(res);
   // cout << res << endl;
    for (int i = 0; i < n; ++ i)
    {
       // cout << a[i] << " ";
        pos[a[i]] = i;
    }
   // cout << endl;
    vector < pair < int, int > > u;
    for (int i = 0; i < n; ++ i)
    {
        if(a[i] == i)continue;
        u.pb(make_pair(pos[i], i));
       // cout << "swap " << i << " " << pos[i] << endl;

        int val1 = a[i];
        int val2 = a[pos[i]];
        int index1 = i;
        int index2 = pos[i];
        a[index1] = val2;
        pos[val2] = index1;

        a[index2] = val1;
        pos[val1] = index2;

    }

    for (int i = 0; i < res; ++ i)
    {
        swap(val[sx[i]], val[sy[i]]);
        if(u.size() == 0)break;
        pair < int, int > curr = u.back();
        u.pop_back();
        P[i] = val[curr.first];
        Q[i] = val[curr.second];
        swap(val[curr.first], val[curr.second]);

    }
	return res;
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26