Submission #1269620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269620		vtnoo	Sorting (IOI15_sorting)	C++20	100 / 100	191 ms	22320 KiB

sorting

#include <bits/stdc++.h>
#define ll int
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
 
bool isOrd(vector<ll>&v)
{
    ll i;
    for(i=0; i<sz(v); i++)
        if(i!=v[i])
            return 0;
    return 1;
}
vector<ll>x,y,s;
vector<ll>in, m, v, mal;
void can(ll M, vector<ll>&P, vector<ll>&Q)
{
    ll N=sz(s);
 
    iota(all(in),0);
    ll i, j, k, l, end=N-1;
    for(i=M-1; i>=0; i--)
        swap(in[x[i]],in[y[i]]);
 
    v=s;
    for(i=0; i<N; i++)
    {
        if(v[i]!=in[i])
            mal[v[i]]=i;
        else 
            mal[v[i]]=-1;
        m[in[i]]=i;
    }
 
    for(i=0; i<M; i++)
    {
        if(v[x[i]]!=in[x[i]])
            mal[v[x[i]]]=-1;
        if(v[y[i]]!=in[y[i]])
            mal[v[y[i]]]=-1;
        swap(v[x[i]],v[y[i]]);
        swap(m[in[x[i]]],m[in[y[i]]]);
        swap(in[x[i]],in[y[i]]);
        if(v[x[i]]!=in[x[i]])
            mal[v[x[i]]]=x[i];
        if(v[y[i]]!=in[y[i]])
            mal[v[y[i]]]=y[i];
        while(end>=0&&mal[end]==-1)
            end--;
        if(end>=0)
        {
            k=mal[end];
            l=m[v[k]];
            mal[end]=-1;
            mal[v[l]]=-1;
            if(v[l]!=in[k])
                mal[v[l]]=k;
            swap(v[k],v[l]);
            P[i]=k;
            Q[i]=l;
        }
        else
        {
            P[i]=0;
            Q[i]=0;
        }
    }
    while(end>=0&&mal[end]==-1)
        end--;
    if(end<0)
        return;
    P[0]=-1;
}
 
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    ll l=1, r=(N)-1, piv, pos=(N), i;
    in.resize(N);
    m.resize(N);
    x.resize(M);
    y.resize(M);
    mal.resize(N);
    for(i=0; i<M; i++)
    {
        x[i]=X[i];
        y[i]=Y[i];
    }
    s.resize(N);
    for(i=0; i<N; i++)
        s[i]=S[i];
    if(isOrd(s))
        return 0;
    vector<ll>a(M),b(M);
    while(l<=r)
    {
        piv=(l+r)/2;
        can(piv,a,b);
        if(a[0]!=-1)
        {
            pos=piv;
            r=piv-1;
        }
        else
            l=piv+1;
    }
    vector<ll>p(pos),q(pos);
    can(pos,p,q);
    for(i=0; i<sz(p); i++)
    {
        P[i]=p[i];
        Q[i]=q[i];
    }
	return pos;
}

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