Submission #874584

#	Time	Username	Problem	Language	Result	Execution time	Memory
874584		HuyQuang_re_Zero	Sorting (IOI15_sorting)	C++14	100 / 100	148 ms	39732 KiB

sorting

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "sorting.h"
#define mxn 600005
using namespace std;
int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
int root(int u) { return (u==r[u]) ? u : r[u]=root(r[u]); }
bool check(int k)
{
    for(i=1;i<=n;i++) tg[i]=p[i],r[i]=i;
    int comp=n;
    for(i=1;i<=k;i++) swap(p[x[i]],p[y[i]]);
    for(i=1;i<=n;i++)
        if(root(i)!=root(p[i]))
        {
            r[root(i)]=root(p[i]);
            comp--;
        }
    for(i=1;i<=n;i++) p[i]=tg[i];
    return n-comp<=k;
}
int findSwapPairs(int _n,int _p[],int _m,int _x[],int _y[],int a[],int b[])
{
    n=_n;
    for(i=n;i>=1;i--) p[i]=_p[i-1],p[i]++;
    m=_m;
    for(i=m;i>=1;i--) x[i]=_x[i-1],y[i]=_y[i-1],x[i]++,y[i]++;
    int l=0,r=m;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid; else l=mid+1;
    }

    /////////////////////////////////////////////////////////////////////////////
    for(i=1;i<=n;i++) tg[i]=p[i];
    vector <II> vec;
    for(i=1;i<=l;i++) swap(p[x[i]],p[y[i]]);
    for(i=1;i<=n;i++)
        if(visited[i]==0)
        {
            int u=i;
            while(p[u]!=i)
            {
                //cerr<<u-1<<" "<<p[u]-1<<'\n';
                vec.push_back({ u,p[u] }),u=p[u],visited[u]=1;
            }
            visited[u]=1;
        }
    for(i=1;i<=n;i++) vec.push_back({ i,i });
    reverse(vec.begin(),vec.end());
    for(i=1;i<=n;i++) p[i]=tg[i];
    //////////////////////////////////////////////////////////////////////////////////

    cerr<<'\n';
    for(i=1;i<=n;i++) pos[p[i]]=i;
    int res=0;
    for(i=1;i<=l;i++)
    {
        swap(pos[p[x[i]]],pos[p[y[i]]]);
        swap(p[x[i]],p[y[i]]);
        /*
        cout<<x[i]-1<<" "<<y[i]-1<<'\n';
        for(int i=1;i<=n;i++) cout<<p[i]-1<<" ";
        cout<<'\n';
        */
        int u=pos[vec.back().fst],v=pos[vec.back().snd]; vec.pop_back();
        swap(pos[p[u]],pos[p[v]]);
        swap(p[u],p[v]);
        /*
        cout<<u-1<<" "<<v-1<<'\n';
        for(int i=1;i<=n;i++) cout<<p[i]-1<<" ";
        cout<<'\n';*/
        a[res]=u-1; b[res]=v-1;
        res++;
    }
    return res;
}
/*
int main()
{
    freopen("sorting.inp","r",stdin);
    freopen("sorting.out","w",stdout);
    cin>>n;
    for(i=0;i<n;i++) cin>>p[i];
    cin>>m;
    for(i=0;i<m;i++) cin>>x[i]>>y[i];
    cout<<(res=findSwapPairs(n,p,m,x,y,a,b))<<'\n';
    for(i=0;i<res;i++) cout<<a[i]<<" "<<b[i]<<'\n';
}
*/

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:35:72: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   35 | int findSwapPairs(int _n,int _p[],int _m,int _x[],int _y[],int a[],int b[])
      |                                                                    ~~~~^~~
sorting.cpp:19:80: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                                                                ^
sorting.cpp:35:64: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   35 | int findSwapPairs(int _n,int _p[],int _m,int _x[],int _y[],int a[],int b[])
      |                                                            ~~~~^~~
sorting.cpp:19:73: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                                                         ^
sorting.cpp:41:13: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   41 |     int l=0,r=m;
      |             ^
sorting.cpp:19:33: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                 ^
sorting.cpp:70:9: warning: declaration of 'res' shadows a global declaration [-Wshadow]
   70 |     int res=0;
      |         ^~~
sorting.cpp:19:69: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                                                     ^~~

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