Submission #70140

#	Time	Username	Problem	Language	Result	Execution time	Memory
70140		Vahan	Sorting (IOI15_sorting)	C++17	100 / 100	187 ms	16432 KiB

sorting

#include "sorting.h"
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
vector<pair<int,int> > v;
int n,ps[300000],s[300000],x[300000],y[300000],rev_ps[300000],r[300000];
int qayl_qan()
{
    int q=0;
    for(int i=0;i<n;i++)
        rev_ps[ps[i]]=i;
    for(int i=0;i<n;i++)
    {
        if(ps[rev_ps[i]]==ps[i])
            continue;
        int e=ps[i];
        swap(ps[rev_ps[i]],ps[i]);
        q++;
        swap(rev_ps[i],rev_ps[e]);
    }
    return q;
}
int stug(int e)
{
    for(int i=0;i<n;i++)
        ps[i]=s[i];
    for(int i=0;i<=e;i++)
        swap(ps[x[i]],ps[y[i]]);
    if(qayl_qan()<=e+1)
        return 1;
    else
        return 0;
}
int bin(int l,int r)
{
    if(l==r)
        return r;
    int mid=(l+r)/2;
    if(stug(mid))
        bin(l,mid);
    else
        bin(mid+1,r);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    if(M>=N)
        M=N-1;
    for(int i=0;i<N;i++)
        s[i]=S[i];
    for(int i=0;i<M;i++)
    {
        x[i]=X[i];
        y[i]=Y[i];
    }
    n=N;
    for(int i=0;i<n;i++)
        ps[i]=s[i];
    if(qayl_qan()==0)
        return 0;
    int t=bin(0,M-1);
    t++;
    for(int i=0;i<n;i++)
        ps[i]=s[i];
    for(int i=0;i<t;i++)
        swap(ps[x[i]],ps[y[i]]);
    for(int i=0;i<n;i++)
        rev_ps[ps[i]]=i;
    for(int i=0;i<n;i++)
    {
        if(ps[rev_ps[i]]==ps[i])
            continue;
        int e=ps[i];
        swap(ps[rev_ps[i]],ps[i]);
        v.push_back({ps[i],e});
        swap(rev_ps[i],rev_ps[e]);
    }
    for(int i=0;i<n;i++)
        r[s[i]]=i;
    for(int i=0;i<t;i++)
    {
        swap(s[x[i]],s[y[i]]);
        swap(r[s[x[i]]],r[s[y[i]]]);
        if(v.size()>i)
        {
            P[i]=r[v[i].first];
            Q[i]=r[v[i].second];
        }
        else
        {
            P[i]=0;
            Q[i]=0;
        }
        swap(s[P[i]],s[Q[i]]);
        swap(r[s[P[i]]],r[s[Q[i]]]);
    }
	return t;
}

Compilation message (stderr)

sorting.cpp: In function 'int bin(int, int)':
sorting.cpp:35:20: warning: declaration of 'r' shadows a global declaration [-Wshadow]
 int bin(int l,int r)
                    ^
sorting.cpp:7:63: note: shadowed declaration is here
 int n,ps[300000],s[300000],x[300000],y[300000],rev_ps[300000],r[300000];
                                                               ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(v.size()>i)
            ~~~~~~~~^~
sorting.cpp: In function 'int bin(int, int)':
sorting.cpp:44:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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