oj.uz

Submission #379612

# Submission time Handle Problem Language Result Execution time Memory
379612 2021-03-18T20:09:19 Z idk321 Sorting (IOI15_sorting) C++11
100 / 100
 516 ms 20360 KB 
#include "sorting.h"

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

int n, m;
int* s;
int* x;
int* y;
int* q;
int* p;

bool isOk(int r)
{
    vector<int> change(n);
    for (int i = 0; i < n; i++) change[i] = i;
    for (int i = 0; i <= r; i++)
    {
        swap(change[x[i]], change[y[i]]);
    }
    vector<int> needed(n);
    for (int i = 0; i < n; i++)
    {
        needed[change[i]] = i;
    }

    vector<int> cur(s, s + n);

    vector<int> isOn(n);
    for (int i = 0; i < n; i++)
    {
        isOn[cur[i]] = i;
    }

    int check = 0;
    for (int i = 0; i <= r; i++)
    {
        swap(cur[x[i]], cur[y[i]]);
        swap(needed[x[i]], needed[y[i]]);
        isOn[cur[x[i]]] = x[i];
        isOn[cur[y[i]]] = y[i];


        while (check < n)
        {
            if (check != needed[isOn[check]])
            {
                int a = isOn[check];
                int b = isOn[needed[isOn[check]]];
                swap(cur[a], cur[b]);
                isOn[cur[a]] = a;
                isOn[cur[b]] = b;
                p[i] = a;
                q[i] = b;
                break;
            }

            check++;
        }

        if (check == n)
        {
            p[i] = 0;
            q[i] = 0;
        }
    }



    for (int i = 1; i < n; i++)
    {
        if (cur[i] < cur[i - 1]) return false;
    }
    return true;
}

int bs()
{
    int a = 0;
    int b = m - 1;
    int res = -1;

    while (a <= b)
    {
        int mid = (a + b) / 2;

        if (isOk(mid))
        {
            res = mid;
            b = mid - 1;
        } else
        {
            a = mid + 1;
        }
    }

    return res;
}


int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    m = M;
    s = S;
    x = X;
    y = Y;
    p = P;
    q = Q;

    bool alreadyGood = true;
    for (int i = 1; i < n; i++)
    {
        if (s[i] < s[i - 1]) alreadyGood = false;
    }

    if (alreadyGood) return 0;


    int best = bs();
    isOk(best);



	return best + 1;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 400 ms 10084 KB Output is correct
16 Correct 473 ms 18312 KB Output is correct
17 Correct 515 ms 19232 KB Output is correct
18 Correct 45 ms 13420 KB Output is correct
19 Correct 322 ms 19736 KB Output is correct
20 Correct 336 ms 20184 KB Output is correct
21 Correct 343 ms 20192 KB Output is correct
22 Correct 429 ms 14560 KB Output is correct
23 Correct 476 ms 20052 KB Output is correct
24 Correct 508 ms 19692 KB Output is correct
25 Correct 512 ms 19356 KB Output is correct
26 Correct 329 ms 20348 KB Output is correct
27 Correct 291 ms 19884 KB Output is correct
28 Correct 481 ms 19684 KB Output is correct
29 Correct 464 ms 19592 KB Output is correct
30 Correct 226 ms 19992 KB Output is correct
31 Correct 473 ms 19896 KB Output is correct
32 Correct 454 ms 19180 KB Output is correct
33 Correct 506 ms 19744 KB Output is correct
34 Correct 489 ms 19720 KB Output is correct
35 Correct 314 ms 19364 KB Output is correct
36 Correct 126 ms 20168 KB Output is correct
37 Correct 516 ms 20360 KB Output is correct
38 Correct 494 ms 19604 KB Output is correct
39 Correct 502 ms 19480 KB Output is correct