oj.uz

Submission #99206

# Submission time Handle Problem Language Result Execution time Memory
99206 2019-03-01T17:30:03 Z eriksuenderhauf Sorting (IOI15_sorting) C++11
100 / 100
 748 ms 30724 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "sorting.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
int n = 0, m = 0;
int x[MAXN], y[MAXN], p[MAXN], q[MAXN], sz[MAXN], ind2[MAXN];
int p2[MAXN], q2[MAXN], par[MAXN], a[MAXN], ind[MAXN];

int qry(int x) {
    if (x == par[x]) return x;
    return par[x] = qry(par[x]);
}

void join(int x, int y) {
    x = qry(x), y = qry(y);
    if (x == y) return;
    if (sz[x] > sz[y]) swap(x, y);
    sz[y] += sz[x];
    par[x] = y;
}

bool solve(int cnt) {
    for (int i = 0; i < n; i++)
        par[i] = i, sz[i] = 1, ind[i] = i;
    for (int i = 0; i < cnt; i++) {
        swap(a[x[i]], a[y[i]]);
        swap(ind[x[i]], ind[y[i]]);
    }
    for (int i = 0; i < n; i++)
        join(i, a[i]);
    vii ans;
    int cnt2 = 0;
    for (int i = 0; i < n; i++) {
        if (qry(i) != i)
            continue;
        cnt2 += sz[i] - 1;
        int nx = a[i], pr = i;
        while (nx != i) {
            ans.pb({ind[i], ind[nx]});
            pr = nx;
            nx = a[nx];
        }
    }
    while (ans.size() < cnt)
        ans.pb({0, 0});
    for (int i = 0; i < n; i++)
        ind[i] = i, ind2[i] = i;
    for (int i = 0; i < cnt; i++) {
        swap(ind2[ind[x[i]]], ind2[ind[y[i]]]);
        swap(ind[x[i]], ind[y[i]]);
        p[i] = ind2[ans[i].fi], q[i] = ind2[ans[i].se];
    }
    return (ans.size() == cnt);
}

void cp(int cnt) {
    for (int i = 0; i < cnt; i++)
        p2[i] = p[i], q2[i] = q[i];
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N, m = M;
    int lo = 0, hi = n - 1, ans = -1;
    for (int i = 0; i < m; i++)
        x[i] = X[i], y[i] = Y[i];
    while (lo <= hi) {
        int mi = (lo + hi) / 2;
        for (int i = 0; i < n; i++)
            a[i] = S[i];
        if (solve(mi)) {
            hi = mi - 1, ans = mi;
            cp(ans);
        } else
            lo = mi + 1;
    }
    for (int i = 0; i < ans; i++)
        P[i] = p2[i], Q[i] = q2[i];
    return ans;
}

Compilation message

sorting.cpp: In function 'int qry(int)':
sorting.cpp:19:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int qry(int x) {
              ^
sorting.cpp:16:5: note: shadowed declaration is here
 int x[MAXN], y[MAXN], p[MAXN], q[MAXN], sz[MAXN], ind2[MAXN];
     ^
sorting.cpp: In function 'void join(int, int)':
sorting.cpp:24:23: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 void join(int x, int y) {
                       ^
sorting.cpp:16:14: note: shadowed declaration is here
 int x[MAXN], y[MAXN], p[MAXN], q[MAXN], sz[MAXN], ind2[MAXN];
              ^
sorting.cpp:24:23: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void join(int x, int y) {
                       ^
sorting.cpp:16:5: note: shadowed declaration is here
 int x[MAXN], y[MAXN], p[MAXN], q[MAXN], sz[MAXN], ind2[MAXN];
     ^
sorting.cpp: In function 'bool solve(int)':
sorting.cpp:47:24: warning: variable 'pr' set but not used [-Wunused-but-set-variable]
         int nx = a[i], pr = i;
                        ^~
sorting.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ans.size() < cnt)
            ~~~~~~~~~~~^~~~~
sorting.cpp:63:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return (ans.size() == cnt);
             ~~~~~~~~~~~^~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 372 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 372 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 372 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 3 ms 640 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 4 ms 768 KB Output is correct
22 Correct 2 ms 740 KB Output is correct
23 Correct 4 ms 768 KB Output is correct
24 Correct 4 ms 768 KB Output is correct
25 Correct 4 ms 768 KB Output is correct
26 Correct 4 ms 768 KB Output is correct
27 Correct 5 ms 768 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 5 ms 644 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 4 ms 768 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 6 ms 896 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 3 ms 640 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 5 ms 644 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 4 ms 768 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 6 ms 896 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 3 ms 640 KB Output is correct
15 Correct 549 ms 27224 KB Output is correct
16 Correct 593 ms 27724 KB Output is correct
17 Correct 666 ms 29124 KB Output is correct
18 Correct 107 ms 23708 KB Output is correct
19 Correct 351 ms 26376 KB Output is correct
20 Correct 429 ms 29756 KB Output is correct
21 Correct 539 ms 30012 KB Output is correct
22 Correct 515 ms 24716 KB Output is correct
23 Correct 526 ms 30300 KB Output is correct
24 Correct 597 ms 29940 KB Output is correct
25 Correct 748 ms 29496 KB Output is correct
26 Correct 389 ms 28988 KB Output is correct
27 Correct 366 ms 26384 KB Output is correct
28 Correct 596 ms 29428 KB Output is correct
29 Correct 511 ms 28796 KB Output is correct
30 Correct 221 ms 26716 KB Output is correct
31 Correct 667 ms 29608 KB Output is correct
32 Correct 529 ms 29344 KB Output is correct
33 Correct 592 ms 29904 KB Output is correct
34 Correct 620 ms 29896 KB Output is correct
35 Correct 419 ms 26052 KB Output is correct
36 Correct 121 ms 25540 KB Output is correct
37 Correct 675 ms 30724 KB Output is correct
38 Correct 585 ms 29512 KB Output is correct
39 Correct 579 ms 29832 KB Output is correct