Submission #98239

#	Time	Username	Problem	Language	Result	Execution time	Memory
98239		MvC	정렬하기 (IOI15_sorting)	C++11	0 / 100	3 ms	768 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,pos[202020],a[202020],n,j,xo[602020],yo[602020];
bool sor()
{
    ll ii;
    for(ii=0;ii<n;ii++)if(a[ii]!=ii)return 0;
    return 1;
}
ll te=0;
ll mir[202020],m;
ll Pmir[202020],ta,tb,taa,tbb,P[202020];
ll cari(ll aa)
{
    if(P[aa]==aa)return aa;
    else
    {
        ll temp=cari(P[aa]);
        P[aa]=temp;
        return P[aa];
    }
}
ll bisa(ll aa)
{
    ll ii,H=0;
    for(ii=0;ii<n;ii++)P[ii]=ii;
    for(ii=0;ii<aa;ii++)
    {
        swap(a[xo[ii]],a[yo[ii]]);
        pos[a[xo[ii]]]=xo[ii];
        pos[a[yo[ii]]]=yo[ii];
    }
    for(ii=0;ii<n;ii++)
    {
        //cout<<i<<" "<<ii<<" "<<a[ii]<<"\n";
        ta=ii;
        tb=a[ii];
        taa=cari(ta);
        tbb=cari(tb);
        if(taa!=tbb)
        {
            H++;
            P[taa]=tbb;
        }
    }
    return (aa>=H);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N;
    for(i=0;i<M;i++)xo[i]=X[i];
    for(i=0;i<M;i++)yo[i]=Y[i];
    for(j=0;j<N;j++)a[j]=S[j];
    for(j=0;j<N;j++)pos[S[j]]=j;
    if(sor())return 0;
    ll L=1,R=N,C;
    while(L<=R)
    {
        C=(L+R)/2;
        for(j=0;j<N;j++)a[j]=S[j];
        for(j=0;j<N;j++)pos[S[j]]=j;
        ll O=bisa(C);
        if(O)
        {
            m=C;
            R=C-1;
        }
        else
            L=C+1;
    }
   // cout<<"M"<<m<<"\n";
 
    return m;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:54:76: warning: declaration of 'P' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                                                            ^
sorting.cpp:18:31: note: shadowed declaration is here
 ll Pmir[202020],ta,tb,taa,tbb,P[202020];
                               ^
sorting.cpp:78:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return m;
            ^
sorting.cpp:54:66: warning: unused parameter 'P' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                                                  ^
sorting.cpp:54:75: warning: unused parameter 'Q' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                                                           ^

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