Submission #197507

#	Time	Username	Problem	Language	Result	Execution time	Memory
197507		handlename	Sorting (IOI15_sorting)	C++17	100 / 100	337 ms	28352 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
int n,m;
pair<int,int> brr[600001];
int ori[200001],arr[200001],pos[200001];
vector<pair<int,int> > val;
bool works(int k){
    val.clear();
    for (int i=0;i<n;i++) arr[i]=ori[i];
    for (int i=0;i<k;i++) swap(arr[brr[i].first],arr[brr[i].second]);
    for (int i=0;i<n;i++){
        pos[arr[i]]=i;
    }
    for (int i=0;i<n;i++){
        if (arr[i]!=i){
            int one=i;
            int two=pos[i];
            swap(arr[one],arr[two]);
            val.push_back(make_pair(arr[one],arr[two]));
            pos[i]=i;
            pos[arr[two]]=two;
        }
    }
    if (val.size()>k) return false;
    while (val.size()<k) val.push_back(make_pair(0,0));
    return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N;
    m=M;
    for (int i=0;i<n;i++) ori[i]=S[i];
    for (int i=0;i<m;i++) brr[i]=make_pair(X[i],Y[i]);
    int mini=-1,maxi=m;
    while (mini+1<maxi){
        int mid=(mini+maxi)/2;
        if (works(mid)) maxi=mid;
        else mini=mid;
    }
    works(maxi);
    for (int i=0;i<n;i++) arr[i]=ori[i];
    for (int i=0;i<n;i++) pos[arr[i]]=i;
    for (int i=0;i<maxi;i++){
        int a=X[i];
        int b=Y[i];
        swap(arr[a],arr[b]);
        swap(pos[arr[a]],pos[arr[b]]);
        int one=val[i].first;
        int two=val[i].second;
        a=pos[one];
        b=pos[two];
        P[i]=a;
        Q[i]=b;
        swap(pos[arr[a]],pos[arr[b]]);
        swap(arr[a],arr[b]);
    }
    return maxi;
}

Compilation message (stderr)

sorting.cpp: In function 'bool works(int)':
sorting.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (val.size()>k) return false;
         ~~~~~~~~~~^~
sorting.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (val.size()<k) val.push_back(make_pair(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