Submission #68696

#	Time	Username	Problem	Language	Result	Execution time	Memory
68696		MANcity	Sorting (IOI15_sorting)	C++14	100 / 100	311 ms	13308 KiB

sorting

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "sorting.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int t[200002];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int u=0;
    for0(i,N-1)
        if(S[i]!=i)
            u=1;
    if(u==0)
        return 0;
    int l=0;
    int r=(M-1);
    while(1)
    {
        if(l==r)
        {
            pair<int,int> NS[200002];
            int pos[200002];
            for0(i,N-1)
                NS[i]=mp(S[i],i);

            for0(i,l)
            {
                pair<int,int> t=NS[Y[i]];
                NS[Y[i]]=NS[X[i]];
                NS[X[i]]=t;
            }
            for0(i,N-1)
                pos[NS[i].first]=i;
            vector<pair<int,int> > ans;
            for0(i,N-1)
            {
                if(NS[i].first!=i)
                {
                    int t=pos[i];
                    ans.push_back({NS[i].first,NS[t].first});
                    pos[NS[i].first]=t;
                    pos[i]=i;
                    pair<int,int> c=NS[t];
                    NS[t]=NS[i];
                    NS[i]=c;
                }
            }
            int H[200002];
            pos[200002];
            for0(i,N-1)
                H[i]=S[i];
            for0(i,N-1)
                pos[H[i]]=i;
            for0(i,l)
            {
                pos[H[X[i]]]=Y[i];
                pos[H[Y[i]]]=X[i];
                int t=H[Y[i]];
                H[Y[i]]=H[X[i]];
                H[X[i]]=t;
                P[i]=pos[ans[i].first];
                Q[i]=pos[ans[i].second];
                pos[H[P[i]]]=Q[i];
                pos[H[Q[i]]]=P[i];
                t=H[Q[i]];
                H[Q[i]]=H[P[i]];
                H[P[i]]=t;
            }
            return (l+1);
        }
        int m=(l+r)/2;
        int NS[200002];
        int pos[200002];
        for0(i,N-1)
            NS[i]=S[i];
        for0(i,m)
        {
            int p=NS[Y[i]];
            NS[Y[i]]=NS[X[i]];
            NS[X[i]]=p;
        }
        for0(i,N-1)
            pos[NS[i]]=i;
        int q=0;
        for0(i,N-1)
        {
            if(NS[i]!=i)
            {
                q++;
                pos[NS[i]]=pos[i];
                NS[pos[i]]=NS[i];
                NS[i]=i;
                pos[i]=i;
            }
        }
        if(q>(m+1))
            l=(m+1);
        else
            r=m;
    }
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:45:31: warning: declaration of 't' shadows a global declaration [-Wshadow]
                 pair<int,int> t=NS[Y[i]];
                               ^
sorting.cpp:24:5: note: shadowed declaration is here
 int t[200002];
     ^
sorting.cpp:56:25: warning: declaration of 't' shadows a global declaration [-Wshadow]
                     int t=pos[i];
                         ^
sorting.cpp:24:5: note: shadowed declaration is here
 int t[200002];
     ^
sorting.cpp:66:23: warning: statement has no effect [-Wunused-value]
             pos[200002];
             ~~~~~~~~~~^
sorting.cpp:75:21: warning: declaration of 't' shadows a global declaration [-Wshadow]
                 int t=H[Y[i]];
                     ^
sorting.cpp:24:5: note: shadowed declaration is here
 int t[200002];
     ^

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