답안 #330258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330258	2020-11-24T09:56:06 Z	mihai145	정렬하기 (IOI15_sorting)	C++14	100 / 100	410 ms	40236 KB

sorting

#include "sorting.h"
#include <vector>

const int NMAX = 2e5;
const int MMAX = 30 * NMAX;

int n, s[NMAX + 2], aux[NMAX + 2], inv[NMAX + 2];
int x[MMAX + 2], y[MMAX + 2];

bool vis[NMAX + 2];
std::vector <int> curr;
std::vector < std::vector <int> > cycles;

void dfs(int node)
{
    vis[node] = 1;
    curr.push_back(node);

    if(!vis[aux[node]])
        dfs(aux[node]);
}

bool Sorted(int limit)
{
    for(int i = 0; i < n; i++)
        aux[i] = s[i], vis[i] = 0;

    for(int i = 0; i < limit; i++)
        std::swap(aux[x[i]], aux[y[i]]);

    cycles.clear();
    for(int i = 0; i < n; i++)
        if(!vis[i])
        {
            curr.clear();
            dfs(i);
            cycles.push_back(curr);
        }

    int t = 0;
    for(auto it : cycles)
        t += ((int)it.size() - 1);

    return (t <= limit);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    n = N;
    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 st = 0, dr = N, sol = -1;

    while(st <= dr)
    {
        int mid = (st + dr) >> 1;

        if(Sorted(mid))
        {
            sol = mid;
            dr = mid - 1;
        }
        else
        {
            st = mid + 1;
        }
    }

    ///to reconstruct the cycles
    Sorted(sol);

    std::vector < std::pair<int,int> > moves;
    for(auto it : cycles)
    {
        for(int i = 0; i < (int)it.size() - 1; i++)
        {
            moves.push_back({it[i], it[i + 1]});
        }
    }

    for(int i = 0; i < n; i++)
    {
        inv[s[i]] = i;
    }

    for(int i = 0; i < sol; i++)
    {
        int preX = s[X[i]];
        int preY = s[Y[i]];

        inv[preX] = Y[i];
        inv[preY] = X[i];

        std::swap(s[X[i]], s[Y[i]]);

        if(!moves.empty())
        {
            P[i] = inv[moves.back().first];
            Q[i] = inv[moves.back().second];
            moves.pop_back();
        }
        else
        {
            P[i] = Q[i] = 0;
        }
    }

    return sol;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	0 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	0 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	0 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	0 ms	364 KB	Output is correct
6	Correct	0 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	0 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

#	결과	실행 시간	메모리	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	384 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	0 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	0 ms	364 KB	Output is correct
6	Correct	0 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	0 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	384 KB	Output is correct
19	Correct	0 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	748 KB	Output is correct
22	Correct	1 ms	748 KB	Output is correct
23	Correct	2 ms	748 KB	Output is correct
24	Correct	1 ms	748 KB	Output is correct
25	Correct	2 ms	748 KB	Output is correct
26	Correct	2 ms	748 KB	Output is correct
27	Correct	1 ms	748 KB	Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	620 KB	Output is correct
2	Correct	2 ms	748 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	3 ms	620 KB	Output is correct
5	Correct	3 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	3 ms	748 KB	Output is correct
8	Correct	2 ms	748 KB	Output is correct
9	Correct	2 ms	748 KB	Output is correct
10	Correct	2 ms	748 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	3 ms	620 KB	Output is correct
13	Correct	2 ms	760 KB	Output is correct
14	Correct	2 ms	620 KB	Output is correct
15	Correct	188 ms	29156 KB	Output is correct
16	Correct	197 ms	32212 KB	Output is correct
17	Correct	214 ms	32900 KB	Output is correct
18	Correct	410 ms	30480 KB	Output is correct
19	Correct	359 ms	32272 KB	Output is correct
20	Correct	356 ms	34588 KB	Output is correct
21	Correct	351 ms	35356 KB	Output is correct
22	Correct	172 ms	23672 KB	Output is correct
23	Correct	205 ms	34616 KB	Output is correct
24	Correct	215 ms	33244 KB	Output is correct
25	Correct	211 ms	33040 KB	Output is correct
26	Correct	339 ms	31900 KB	Output is correct
27	Correct	345 ms	32028 KB	Output is correct
28	Correct	257 ms	33928 KB	Output is correct
29	Correct	249 ms	27268 KB	Output is correct
30	Correct	339 ms	33552 KB	Output is correct
31	Correct	254 ms	35112 KB	Output is correct
32	Correct	215 ms	33400 KB	Output is correct
33	Correct	217 ms	34116 KB	Output is correct
34	Correct	189 ms	26516 KB	Output is correct
35	Correct	329 ms	31888 KB	Output is correct
36	Correct	346 ms	32528 KB	Output is correct
37	Correct	245 ms	40236 KB	Output is correct
38	Correct	232 ms	39104 KB	Output is correct
39	Correct	241 ms	39220 KB	Output is correct

답안 #330258

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