oj.uz

Submission #712185

# Submission time Handle Problem Language Result Execution time Memory
712185 2023-03-18T10:26:04 Z neki Sorting (IOI15_sorting) C++14
54 / 100
 2 ms 596 KB 
#include <bits/stdc++.h>
// #include "sorting.h"
#define vc vector

using namespace std;

int findSwapPairs(int n, int s[], int m, int x[], int y[], int a[], int b[])
{
    int is[n];
    for (int i = 0; i < n; ++i)
        is[s[i]] = i;

    function<bool(int)> solve = [&](int meja)
    {
        int p[n], ip[n], z[n], iz[n];
        for (int i = 0; i < n; ++i)
            p[i] = i, z[i] = iz[i] = i;
        for (int i = meja - 1; i >= 0; --i)
            swap(p[x[i]], p[y[i]]);
        for (int i = 0; i < n; ++i)
            ip[p[i]] = i;

        int j = 0;
        for (int i = meja - 1; i >= 0; --i)
        {
            /*for (int t = 0; t < n; ++t)
                cout << z[t] << " ";
            cout << endl;*/
            while (j < n && j == s[ip[iz[j]]])
                ++j;
            if (j < n)
                a[i] = iz[j], b[i] = p[is[j]];
            else
                a[i] = b[i] = 0;

            swap(iz[z[a[i]]], iz[z[b[i]]]);
            swap(z[a[i]], z[b[i]]);

            /*cout << "prej" << endl;
            for (int t = 0; t < n; ++t)
                cout << s[ip[iz[t]]] << " ";
            cout << endl;*/

            swap(iz[z[x[i]]], iz[z[y[i]]]);
            swap(z[x[i]], z[y[i]]);

            swap(p[ip[x[i]]], p[ip[y[i]]]);
            swap(ip[x[i]], ip[y[i]]);

            /*cout << "po" << endl;
            for (int t = 0; t < n; ++t)
                cout << s[ip[iz[t]]] << " ";
            cout << endl;*/
        }
        while (j < n && j == s[ip[iz[j]]])
            ++j;
        return j == n;
    };

    int l = 1, r = m;
    while (l < r)
    {
        int mid = (l + r) / 2;

        if (solve(mid))
            r = mid;
        else
            l = mid + 1;
    }
    solve(l);
    // solve(l);

    return l;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 308 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 2 ms 588 KB Output is correct
22 Correct 1 ms 572 KB Output is correct
23 Correct 2 ms 572 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 2 ms 572 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 588 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -