Submission #126905

#	Time	Username	Problem	Language	Result	Execution time	Memory
126905		Plurm	Sorting (IOI15_sorting)	C++11	100 / 100	644 ms	23804 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

int target[200005];
int cur[200005];
int bck[200005];
vector<pair<int,int> > computeShortestSwaps(int N, int t[]){
    vector<pair<int,int> > ret;
    for(int i = 0; i < N; i++){
        bck[i] = i;
        cur[i] = i;
    }
    for(int i = 0; i < N; i++){
        if(cur[i] != t[i]){
            int idx1 = i;
            int idx2 = bck[t[i]];
            ret.emplace_back(idx1, idx2);
            bck[cur[idx1]] = idx2;
            bck[cur[idx2]] = idx1;
            swap(cur[idx1], cur[idx2]);
        }
    }
    return ret;
}
int aux[200005];
bool solve(int N, int mid, int S[], int X[], int Y[], int P[], int Q[]){
    for(int i = 0; i < N; i++) cur[i] = i;
    for(int i = 0; i < mid; i++){
        swap(cur[X[i]], cur[Y[i]]);
    }
    for(int i = 0; i < N; i++) bck[cur[i]] = i;
    for(int i = 0; i < N; i++) target[i] = cur[S[i]];
    vector<pair<int,int> > cmds = computeShortestSwaps(N, target);
    if(cmds.size() > mid) return false;
    for(int i = 0; i < N; i++){
        cur[i] = i;
        bck[i] = i;
        aux[i] = i;
        target[i] = i;
    }
    for(int i = 0; i < mid; i++){
        int idx1 = X[i];
        int idx2 = Y[i];
        bck[cur[idx1]] = idx2;
        bck[cur[idx2]] = idx1;
        swap(cur[idx1], cur[idx2]);
        if(i < cmds.size()){
            idx1 = target[cmds[i].first];
            idx2 = target[cmds[i].second];
            target[aux[idx1]] = idx2;
            target[aux[idx2]] = idx1;
            swap(aux[idx1], aux[idx2]);
            idx1 = bck[idx1];
            idx2 = bck[idx2];
            P[i] = idx1;
            Q[i] = idx2;
        }else{
            P[i] = 0;
            Q[i] = 0;
        }
    }
    return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int lo = 0;
    int hi = M;
    int mid;
    while(lo < hi){
        mid = (lo + hi)/2;
        if(solve(N, mid, S, X, Y, P, Q)){
            hi = mid;
        }else{
            lo = mid+1;
        }
    }
    solve(N, lo, S, X, Y, P, Q);
    return lo;
}

Compilation message (stderr)

sorting.cpp: In function 'bool solve(int, int, int*, int*, int*, int*, int*)':
sorting.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(cmds.size() > mid) return false;
        ~~~~~~~~~~~~^~~~~
sorting.cpp:48:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i < cmds.size()){
            ~~^~~~~~~~~~~~~

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