Submission #1313609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313609		activedeltorre	Sorting (IOI15_sorting)	C++20	20 / 100	1 ms	824 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;
int n;
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)
{
    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 correct=0;
void swp(int a,int b)
{
    if(vec[a]==a)
    {
        correct--;
    }
    if(vec[b]==b)
    {
        correct--;
    }
    swap(vec[a],vec[b]);
    if(vec[a]==a)
    {
        correct++;
    }
    if(vec[b]==b)
    {
        correct++;
    }
}
vector<pair<int,int> > check(vector<pair<int,int> >op)
{
    vector<pair<int,int> >curr;
    for(int i=0;i<n;i++)
    {
        if(vec[i]==i)
        {
            correct++;
        }
    }
    if(correct==n)
    {
        return curr;
    }
    for(int i=0;i<op.size();i++)
    {
        swp(x[i],y[i]);
        swp(op[i].first,op[i].second);
        curr.push_back({op[i].first,op[i].second});
        if(correct==n)
        {
            return curr;
        }
    }
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    n=N;
    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);
    vector<pair<int,int> >rez2=check(rez);
    for(int i=0;i<rez2.size();i++)
    {
        P[i]=rez[i].first;
        Q[i]=rez[i].second;
    }
    return rez2.size();
}

Compilation message (stderr)

sorting.cpp: In function 'std::vector<std::pair<int, int> > check(std::vector<std::pair<int, int> >)':
sorting.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type]
   93 | }
      | ^

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