Submission #666546

#	Time	Username	Problem	Language	Result	Execution time	Memory
666546		jamezzz	Sorting (IOI15_sorting)	C++17	0 / 100	9 ms	500 KiB

sorting

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

#define maxn 200005

int n, t[maxn], pos[maxn], os[maxn];
int *s, *x, *y, *p, *q;

bool can(int k) {
    for (int i = 0; i < n; ++i){
        t[i] = i;
        s[i] = os[i];
        pos[s[i]] = i;
    }
    for (int i = k - 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 < k; ++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 diff.empty();
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    s = S, x = X, y = Y, p = P, q = Q, n = N;
    for(int i = 0; i < n; ++i){
        os[i] = s[i];
    }
    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;
    }
    can(res);
    return res;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:75:12: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |     return 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