Submission #791253

#	Time	Username	Problem	Language	Result	Execution time	Memory
791253		TimDee	Sorting (IOI15_sorting)	C++17	100 / 100	98 ms	21644 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second

int findSwapPairs(int n, int _p[], int m, int x[], int y[], int P[], int Q[]) {

    int z=1;
    forn(i,n) if (_p[i]!=i) z=0;
    if (z) return 0;

    int l=1, r=n; 
    while (l<r) {
        int m=(l+r)>>1;
        vector<int> p(n);
        forn(i,n) p[i]=_p[i];
        forn(i,m) {
            swap(p[x[i]],p[y[i]]);
        }
        vector<int> pos(n);
        forn(i,n) pos[p[i]]=i;

        int z=0;
        forn(i,n) {
            if (p[i]!=i) {
                z++;
                pos[p[i]]=pos[i];
                swap(p[pos[i]],p[i]);
            }
        }
        if (z<=m) r=m;
        else l=m+1;
    }

    for (int k=r; k<=m; ++k) {
        vector<int> p(n);
        forn(i,n) p[i]=_p[i];
        auto a=p;
        forn(i,k) {
            swap(p[x[i]],p[y[i]]);
        }
        vector<int> pos(n);
        forn(i,n) pos[p[i]]=i;

        vector<pi> v;
        forn(i,n) {
            if (p[i]!=i) {
                v.pb({i,p[i]});
                pos[p[i]]=pos[i];
                swap(p[pos[i]],p[i]);
            }
        }

        if (v.size()<=k) {
            while (v.size()<k) v.pb({0,0});
            forn(i,n) pos[a[i]]=i;
            vector<pi> e;
            forn(i,k) {
                swap(pos[a[x[i]]],pos[a[y[i]]]);
                swap(a[x[i]],a[y[i]]);
                e.pb({pos[v[i].f],pos[v[i].s]});
                swap(pos[v[i].f],pos[v[i].s]);
                swap(a[pos[v[i].f]],a[pos[v[i].s]]);
            }
            forn(i,k) P[i]=e[i].f, Q[i]=e[i].s;
            return k;
        }
    }
    return 0;

}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:18:13: warning: declaration of 'int m' shadows a parameter [-Wshadow]
   18 |         int m=(l+r)>>1;
      |             ^
sorting.cpp:10:40: note: shadowed declaration is here
   10 | int findSwapPairs(int n, int _p[], int m, int x[], int y[], int P[], int Q[]) {
      |                                    ~~~~^
sorting.cpp:27:13: warning: declaration of 'z' shadows a previous local [-Wshadow]
   27 |         int z=0;
      |             ^
sorting.cpp:12:9: note: shadowed declaration is here
   12 |     int z=1;
      |         ^
sorting.cpp:58:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |         if (v.size()<=k) {
      |             ~~~~~~~~^~~
sorting.cpp:59:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |             while (v.size()<k) v.pb({0,0});
      |                    ~~~~~~~~^~

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