oj.uz

Submission #285115

# Submission time Handle Problem Language Result Execution time Memory
285115 2020-08-28T10:26:32 Z SamAnd Sorting (IOI15_sorting) C++17
100 / 100
 515 ms 30344 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
const int N = 200005 * 3;

int n, m;
int S[N];
int X[N], Y[N];

int a[N];
int b[N], bb[N];

int uu[N];

int u[N];

bool c[N];

int P[N], Q[N];
bool stg(int q)
{
    for (int i = 0; i < n; ++i)
    {
        a[i] = S[i];
        b[i] = i;
        bb[i] = i;
        c[i] = false;
    }
    for (int i = 0; i < q; ++i)
    {
        swap(b[bb[X[i]]], b[bb[Y[i]]]);
        swap(bb[X[i]], bb[Y[i]]);
    }
    for (int i = 0; i < n; ++i)
    {
        uu[b[i]] = i;
    }
    for (int i = 0; i < n; ++i)
    {
        u[i] = uu[a[i]];
    }

    for (int i = 0; i < n; ++i)
    {
        b[i] = i;
        bb[i] = i;
    }

    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int x = i;
        if (c[x])
            continue;
        vector<int> v;
        c[x] = true;
        while (1)
        {
            x = u[x];
            if (c[x])
                break;
            v.push_back(x);
            c[x] = true;
        }

        for (int j = 0; j < sz(v); ++j)
        {
            swap(b[bb[X[ans]]], b[bb[Y[ans]]]);
            swap(bb[X[ans]], bb[Y[ans]]);

            swap(a[i], a[v[j]]);
            P[ans] = b[i];
            Q[ans] = b[v[j]];
            ans++;
        }
    }
    while (ans < q)
    {
        P[ans] = 0;
        Q[ans] = 0;
        ans++;
    }

    return ans <= q;
}

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)
    {
        ::S[i] = S[i];
    }

    for (int i = 0; i < m; ++i)
    {
        ::X[i] = X[i];
        ::Y[i] = Y[i];
    }

    int l = 0, r = m;
    int ans = -1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (stg(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }

    assert(ans != -1);

    stg(ans);

    for (int i = 0; i < ans; ++i)
    {
        P[i] = ::P[i];
        Q[i] = ::Q[i];
    }

    for (int i = 0; i < ans; ++i)
    {
        swap(S[X[i]], S[Y[i]]);
        swap(S[P[i]], S[Q[i]]);
    }

    for (int i = 0; i < n; ++i)
    {
        if (S[i] != i)
        {
            assert(false);
        }
    }

    return ans;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:92:78: warning: declaration of 'Q' shadows a global declaration [-Wshadow]
   92 | int findSwapPairs(int N_, int S[], int M_, int X[], int Y[], int P[], int Q[])
      |                                                                              ^
sorting.cpp:24:11: note: shadowed declaration is here
   24 | int P[N], Q[N];
      |           ^
sorting.cpp:92:78: warning: declaration of 'P' shadows a global declaration [-Wshadow]
   92 | int findSwapPairs(int N_, int S[], int M_, int X[], int Y[], int P[], int Q[])
      |                                                                              ^
sorting.cpp:24:5: note: shadowed declaration is here
   24 | int P[N], Q[N];
      |     ^
sorting.cpp:92:78: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
   92 | int findSwapPairs(int N_, int S[], int M_, int X[], int Y[], int P[], int Q[])
      |                                                                              ^
sorting.cpp:13:11: note: shadowed declaration is here
   13 | int X[N], Y[N];
      |           ^
sorting.cpp:92:78: warning: declaration of 'X' shadows a global declaration [-Wshadow]
   92 | int findSwapPairs(int N_, int S[], int M_, int X[], int Y[], int P[], int Q[])
      |                                                                              ^
sorting.cpp:13:5: note: shadowed declaration is here
   13 | int X[N], Y[N];
      |     ^
sorting.cpp:92:78: warning: declaration of 'S' shadows a global declaration [-Wshadow]
   92 | int findSwapPairs(int N_, int S[], int M_, int X[], int Y[], int P[], int Q[])
      |                                                                              ^
sorting.cpp:12:5: note: shadowed declaration is here
   12 | int S[N];
      |     ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 260 ms 19720 KB Output is correct
16 Correct 323 ms 27264 KB Output is correct
17 Correct 454 ms 29596 KB Output is correct
18 Correct 136 ms 25304 KB Output is correct
19 Correct 391 ms 28084 KB Output is correct
20 Correct 435 ms 28592 KB Output is correct
21 Correct 370 ms 28696 KB Output is correct
22 Correct 276 ms 24200 KB Output is correct
23 Correct 305 ms 30128 KB Output is correct
24 Correct 451 ms 30220 KB Output is correct
25 Correct 429 ms 30344 KB Output is correct
26 Correct 391 ms 28144 KB Output is correct
27 Correct 302 ms 27512 KB Output is correct
28 Correct 436 ms 29216 KB Output is correct
29 Correct 492 ms 28920 KB Output is correct
30 Correct 261 ms 26912 KB Output is correct
31 Correct 515 ms 29304 KB Output is correct
32 Correct 291 ms 29104 KB Output is correct
33 Correct 419 ms 30200 KB Output is correct
34 Correct 342 ms 29304 KB Output is correct
35 Correct 345 ms 27808 KB Output is correct
36 Correct 93 ms 26104 KB Output is correct
37 Correct 430 ms 30012 KB Output is correct
38 Correct 417 ms 29700 KB Output is correct
39 Correct 419 ms 29088 KB Output is correct