Submission #448553

#	Time	Username	Problem	Language	Result	Execution time	Memory
448553		FEDIKUS	Sorting (IOI15_sorting)	C++17	100 / 100	200 ms	22568 KiB

sorting

#include "sorting.h"

#include<bits/stdc++.h>
#define xx first
#define yy second

using namespace std;

typedef pair<int,int> pii;

const int maxn=2e5+10;

int novi[maxn];
bool bio[maxn];

bool moze(int mid,int n,int m,int* s,int* x,int* y){
    for(int i=0;i<n;i++) novi[i]=s[i];
    for(int i=0;i<mid;i++){
        swap(novi[x[i]],novi[y[i]]);
    }
    int klk=n;
    for(int i=0;i<n;i++) bio[i]=false;
    for(int i=0;i<n;i++){
        if(bio[i]) continue;
        klk--;
        int tren=novi[i];
        while(tren!=i){
            bio[tren]=true;
            tren=novi[tren];
        }
    }
    return klk<=mid;
}

void swapovi(vector<int> niz,vector<pii> &svi){
    for(int i=0;i<niz.size()-1;i++){
        svi.push_back(make_pair(niz[i],niz[i+1]));
    }
}

int gde[maxn];

vector<pii> popravi(int n,int naj,int* s,int* x,int* y,vector<pii> svi){
    for(int i=0;i<n;i++) novi[i]=s[i];
    for(int i=0;i<n;i++) gde[novi[i]]=i;
    vector<pii> ret;
    for(int i=0;i<naj;i++){
        swap(novi[x[i]],novi[y[i]]);
        gde[novi[x[i]]]=x[i];
        gde[novi[y[i]]]=y[i];
        if(i<svi.size()){
            ret.push_back(make_pair(gde[svi[i].xx],gde[svi[i].yy]));
            int prvi=gde[svi[i].xx];
            int drugi=gde[svi[i].yy];
            swap(novi[prvi],novi[drugi]);
            gde[novi[prvi]]=prvi;
            gde[novi[drugi]]=drugi;
        }else ret.push_back(make_pair(0,0));
    }
    return ret;
}

void nadji(int naj,int n,int m,int* s,int* x,int* y,int* p,int* q){
    for(int i=0;i<n;i++) novi[i]=s[i];
    for(int i=0;i<naj;i++) swap(novi[x[i]],novi[y[i]]);
    int klk=n;
    for(int i=0;i<n;i++) bio[i]=false;
    vector<pii> svi;
    for(int i=0;i<n;i++){
        if(bio[i]) continue;
        vector<int> sada;
        klk--;
        int tren=novi[i];
        sada.push_back(i);
        while(tren!=i){
            sada.push_back(tren);
            bio[tren]=true;
            tren=novi[tren];
        }
        swapovi(sada,svi);
    }
    ///
    vector<pii> res=popravi(n,naj,s,x,y,svi);
    for(int i=0;i<res.size();i++){
        p[i]=res[i].xx;
        q[i]=res[i].yy;
    }
}

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    int l=0;
    int r=m;
    int naj=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(moze(mid,n,m,s,x,y)){
            naj=mid;
            r=mid-1;
        }else l=mid+1;
    }
    nadji(naj,n,m,s,x,y,p,q);
	return naj;
}

Compilation message (stderr)

sorting.cpp: In function 'bool moze(int, int, int, int*, int*, int*)':
sorting.cpp:16:29: warning: unused parameter 'm' [-Wunused-parameter]
   16 | bool moze(int mid,int n,int m,int* s,int* x,int* y){
      |                         ~~~~^
sorting.cpp: In function 'void swapovi(std::vector<int>, std::vector<std::pair<int, int> >&)':
sorting.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<niz.size()-1;i++){
      |                 ~^~~~~~~~~~~~~
sorting.cpp: In function 'std::vector<std::pair<int, int> > popravi(int, int, int*, int*, int*, std::vector<std::pair<int, int> >)':
sorting.cpp:51:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if(i<svi.size()){
      |            ~^~~~~~~~~~~
sorting.cpp: In function 'void nadji(int, int, int, int*, int*, int*, int*, int*)':
sorting.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<res.size();i++){
      |                 ~^~~~~~~~~~~
sorting.cpp:63:30: warning: unused parameter 'm' [-Wunused-parameter]
   63 | void nadji(int naj,int n,int m,int* s,int* x,int* y,int* p,int* q){
      |                          ~~~~^

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