Submission #434918

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
434918	2021-06-22T09:22:38 Z	alextodoran	Sorting (IOI15_sorting)	C++17	100 / 100	245 ms	21060 KB

sorting

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "sorting.h"

using namespace std;

typedef long long ll;

const int N_MAX = 200000;
const int M_MAX = 600000;

int findSwapPairs (int n, int p[], int m, int x[], int y[], int a[], int b[])
{
    function <int ()> minSwaps = [&] ()
    {
        int aux[n];
        int pos[n];
        for(int i = 0; i < n; i++)
        {
            aux[i] = p[i];
            pos[aux[i]] = i;
        }

        int swaps = 0;
        for(int i = 0; i < n; i++)
        {
            if(aux[i] != i)
            {
                int u = i, v = pos[i];
                swap(aux[u], aux[v]);
                swap(pos[aux[u]], pos[aux[v]]);
                swaps++;
            }
        }
        return swaps;
    };

    function <bool (int)> check = [&] (int swaps)
    {
        for(int i = 0; i < swaps; i++)
            swap(p[x[i]], p[y[i]]);

        bool answer = (minSwaps() <= swaps);

        for(int i = swaps - 1; i >= 0; i--)
            swap(p[x[i]], p[y[i]]);

        return answer;
    };

    int swaps;
    {
        int l = 0, r = m;
        while(l < r)
        {
            int mid = (l + r) / 2;
            if(check(mid) == true)
                r = mid;
            else
                l = mid + 1;
        }
        swaps = l;
    }

    {
        int aux[n];
        for(int i = 0; i < n; i++)
            aux[i] = p[i];
        for(int i = 0; i < swaps; i++)
            swap(aux[x[i]], aux[y[i]]);
        int pos[n];
        for(int i = 0; i < n; i++)
            pos[aux[i]] = i;
        int root[n];
        for(int i = 0; i < n; i++)
            root[p[i]] = i;

        int curr = 0;
        for(int i = 0; i < n; i++)
        {
            if(aux[i] != i)
            {
                swap(p[x[curr]], p[y[curr]]);
                swap(root[p[x[curr]]], root[p[y[curr]]]);

                int u = i, v = pos[i];
                swap(aux[u], aux[v]);
                swap(pos[aux[u]], pos[aux[v]]);
                a[curr] = root[aux[u]];
                b[curr] = root[aux[v]];

                swap(p[a[curr]], p[b[curr]]);
                swap(root[p[a[curr]]], root[p[b[curr]]]);

                curr++;
            }
        }
        while(curr < swaps)
        {
            a[curr] = 0;
            b[curr] = 0;
            curr++;
        }
    }
    return swaps;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	332 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	2 ms	332 KB	Output is correct
5	Correct	2 ms	432 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	3 ms	332 KB	Output is correct
8	Correct	2 ms	368 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	2 ms	332 KB	Output is correct
13	Correct	2 ms	432 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	184 ms	18508 KB	Output is correct
16	Correct	199 ms	19068 KB	Output is correct
17	Correct	239 ms	20036 KB	Output is correct
18	Correct	74 ms	15428 KB	Output is correct
19	Correct	164 ms	18320 KB	Output is correct
20	Correct	172 ms	19024 KB	Output is correct
21	Correct	168 ms	19012 KB	Output is correct
22	Correct	192 ms	15300 KB	Output is correct
23	Correct	204 ms	20740 KB	Output is correct
24	Correct	232 ms	20432 KB	Output is correct
25	Correct	221 ms	20164 KB	Output is correct
26	Correct	175 ms	19012 KB	Output is correct
27	Correct	155 ms	18288 KB	Output is correct
28	Correct	226 ms	20292 KB	Output is correct
29	Correct	220 ms	19780 KB	Output is correct
30	Correct	116 ms	17708 KB	Output is correct
31	Correct	245 ms	20164 KB	Output is correct
32	Correct	223 ms	20164 KB	Output is correct
33	Correct	220 ms	20472 KB	Output is correct
34	Correct	210 ms	20436 KB	Output is correct
35	Correct	189 ms	18100 KB	Output is correct
36	Correct	67 ms	16548 KB	Output is correct
37	Correct	237 ms	21060 KB	Output is correct
38	Correct	222 ms	20216 KB	Output is correct
39	Correct	203 ms	20460 KB	Output is correct

Submission #434918

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 20.0 / 20.0

Subtask #6 26.0 / 26.0

Subtask #1
8.0 / 8.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
20.0 / 20.0

Subtask #6
26.0 / 26.0