Submission #1313536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313536		activedeltorre	Sorting (IOI15_sorting)	C++20	20 / 100	1 ms	568 KiB

sorting

#include "sorting.h"
#include <iostream>
#include <vector>
using namespace std;
int x[200005];
int y[200005];
int vec[200005];
int vec2[200005];
int fre[200005];
vector<int>ciclu;
void dfs(int poz)
{
    if(fre[poz]==1)
    {
        return;
    }
    fre[poz]=1;
    ciclu.push_back(poz);
    dfs(vec2[poz]);
}
vector<pair<int,int> > solve(int nroper,int n)
{
    vector<pair<int,int>>oper;
    for(int i=0;i<n;i++)
    {
        fre[i]=0;
        vec2[i]=vec[i];
    }
    /*
    for(int i=0;i<nroper;i++)
    {
        swap(vec2[x[i]],vec2[y[i]]);
    }*/
    for(int i=0;i<n;i++)
    {
        if(fre[i]==0)
        {
            ciclu.clear();
            dfs(i);
            for(int j=1;j<ciclu.size();j++)
            {
                oper.push_back({ciclu[0],ciclu[j]});
            }
        }
    }
    return oper;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    for(int i=0; i<N; i++)
    {
        vec[i]=S[i];
    }
    for(int i=0; i<M; i++)
    {
        x[i]=X[i];
        y[i]=Y[i];
    }
    vector<pair<int,int> >rez=solve(M,N);
    for(int i=0;i<rez.size();i++)
    {
        P[i]=rez[i].first;
        Q[i]=rez[i].second;
    }
    return rez.size();
}

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