답안 #712186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
712186	2023-03-18T10:29:02 Z	neki	정렬하기 (IOI15_sorting)	C++14	100 / 100	501 ms	23412 KB

sorting

#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 = 0, 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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 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	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 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	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	2 ms	468 KB	Output is correct
22	Correct	2 ms	468 KB	Output is correct
23	Correct	2 ms	468 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	468 KB	Output is correct
27	Correct	2 ms	468 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	2 ms	444 KB	Output is correct
8	Correct	2 ms	472 KB	Output is correct
9	Correct	2 ms	436 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	2 ms	468 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	2 ms	444 KB	Output is correct
8	Correct	2 ms	472 KB	Output is correct
9	Correct	2 ms	436 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	2 ms	468 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	316 ms	20516 KB	Output is correct
16	Correct	354 ms	21048 KB	Output is correct
17	Correct	397 ms	22336 KB	Output is correct
18	Correct	98 ms	19148 KB	Output is correct
19	Correct	245 ms	21504 KB	Output is correct
20	Correct	261 ms	22244 KB	Output is correct
21	Correct	294 ms	22116 KB	Output is correct
22	Correct	370 ms	17552 KB	Output is correct
23	Correct	501 ms	22988 KB	Output is correct
24	Correct	488 ms	22660 KB	Output is correct
25	Correct	464 ms	22424 KB	Output is correct
26	Correct	305 ms	22016 KB	Output is correct
27	Correct	268 ms	21472 KB	Output is correct
28	Correct	406 ms	22640 KB	Output is correct
29	Correct	376 ms	22168 KB	Output is correct
30	Correct	173 ms	21208 KB	Output is correct
31	Correct	379 ms	22616 KB	Output is correct
32	Correct	358 ms	22284 KB	Output is correct
33	Correct	396 ms	22664 KB	Output is correct
34	Correct	382 ms	22600 KB	Output is correct
35	Correct	254 ms	21180 KB	Output is correct
36	Correct	76 ms	20456 KB	Output is correct
37	Correct	445 ms	23412 KB	Output is correct
38	Correct	379 ms	22492 KB	Output is correct
39	Correct	401 ms	22556 KB	Output is correct

답안 #712186

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