Submission #666545

#	Time	Username	Problem	Language	Result	Execution time	Memory
666545		jamezzz	Sorting (IOI15_sorting)	C++17	0 / 100	2 ms	468 KiB

sorting

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

#define maxn 200005

int n, t[maxn], vis[maxn], pos[maxn];
int *s, *x, *y;

bool can(int k) {
    for (int i = 0; i < n; ++i) {
        vis[i] = false;
        t[i] = s[i];
    }
    for (int i = 0; i < k; ++i) {
        swap(t[x[i]], t[y[i]]);
    }
    int need = 0;
    for (int i = 0; i < n; ++i) {
        if (vis[i]) continue;
        int cur = i, num = 0;
        while (t[cur] != i) {
            vis[cur] = vis[t[cur]] = true;
            cur = t[cur];
            ++num;
        }
        need += num;
    }
    return need <= k;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    s = S, x = X, y = Y, n = N;
    int lo = 0, hi = M, mid, res;
    while (lo <= hi) {
        mid = (lo + hi) >> 1;
        if (can(mid)) res = mid, hi = mid - 1;
        else lo = mid + 1;
    }
    for (int i = 0; i < n; ++i){
        t[i] = i;
        pos[s[i]] = i;
    }
    for (int i = res - 1; i >= 0; --i){
        swap(t[x[i]], t[y[i]]);
    }
    set<pair<int, int>> diff;
    for (int i = 0; i < n; ++i){
        if (s[i] != t[i]){
            diff.insert({i, s[i]});
        }
    }
    for (int i = 0; i < res; ++i) {
        //for (auto[a, b]: diff)printf("(%d %d) ", a, b); printf("\n");
        //printf("pos: "); for (int i = 0; i < n; ++i) printf("%d ", pos[i]); printf("\n");
        //printf("t: "); for (int i = 0; i < n; ++i) printf("%d ", t[i]); printf("\n");
        if (diff.empty()){
            P[i] = Q[i] = 0;
            continue;
        }
        auto [u, su] = *diff.begin();
        diff.erase(diff.begin());
        int v = pos[t[u]]; 
        int sv = s[v];
        diff.erase({v, sv});
        //printf("u: %d, su: %d, v: %d, sv: %d\n", u, su, v, sv);
        if (t[u] != sv){
            diff.insert({u, sv});
        }
        //for (auto[a, b]: diff)printf("(%d %d) ", a, b); printf("\n");
        P[i] = u; Q[i] = v;
        swap(s[u], s[v]);
        swap(pos[su], pos[sv]);
        //printf("pos: "); for (int i = 0; i < n; ++i) printf("%d ", pos[i]); printf("\n");
        //printf("t: "); for (int i = 0; i < n; ++i) printf("%d ", t[i]); printf("\n");
        
        swap(t[x[i]], t[y[i]]);
        if (diff.find({x[i], s[x[i]]}) != diff.end()){
            diff.erase(diff.find({x[i], s[x[i]]}));
            diff.insert({y[i], s[x[i]]});
        }
        if (diff.find({y[i], s[y[i]]}) != diff.end()){
            diff.erase(diff.find({y[i], s[y[i]]}));
            diff.insert({x[i], s[y[i]]});
        }
        swap(s[x[i]], s[y[i]]);
        swap(pos[s[x[i]]], pos[s[y[i]]]);
    }
    return res;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:34:30: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |     int lo = 0, hi = M, mid, res;
      |                              ^~~

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