oj.uz

Submission #330258

# Submission time Handle Problem Language Result Execution time Memory
330258 2020-11-24T09:56:06 Z mihai145 Sorting (IOI15_sorting) C++14
100 / 100
 410 ms 40236 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# 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 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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