oj.uz

Submission #1059203

# Submission time Handle Problem Language Result Execution time Memory
1059203 2024-08-14T18:39:05 Z andrei_iorgulescu Sorting (IOI15_sorting) C++14
100 / 100
 163 ms 33168 KB 
#include <bits/stdc++.h>
#include "sorting.h"
#warning That's not FB, that's my FB

using namespace std;

int n;
bool viz[200005];
vector<int> lols;
vector<vector<int>> cicli;
vector<int> cur;

void dfs(int nod)
{
    viz[nod] = true;
    cur.push_back(nod);
    if (!viz[lols[nod]])
        dfs(lols[nod]);
}

int cnt_cyc(vector<int> s)
{
    cicli.clear();
    lols = s;
    memset(viz, 0, sizeof(viz));
    for (int i = 0; i < n; i++)
    {
        if (!viz[i])
        {
            cur.clear();
            dfs(i);
            cicli.push_back(cur);
        }
    }
    return cicli.size();
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    n = N;
    int st = -1, pas = 1 << 17;
    while (pas != 0)
    {
        if (st + pas <= M)
        {
            vector<int> s(N);
            for (int i = 0; i < N; i++)
                s[i] = S[i];
            for (int i = 0; i < st + pas; i++)
                swap(s[X[i]], s[Y[i]]);
            if (n - cnt_cyc(s) > st + pas)
                st += pas;
        }
        pas /= 2;
    }
    st++;
    int ans = st;
    vector<pair<int,int>> req_swaps;
    vector<int> s(N);
    for (int i = 0; i < N; i++)
        s[i] = S[i];
    for (int i = 0; i < st + pas; i++)
        swap(s[X[i]], s[Y[i]]);
    int useless = cnt_cyc(s);
    for (int i = 0; i < useless; i++)
        for (int j = (int)cicli[i].size() - 2; j >= 0; j--)
            req_swaps.push_back({cicli[i].back(),cicli[i][j]});
    vector<int> pos(N);
    for (int i = 0; i < N; i++)
        pos[S[i]] = i;
    for (int i = req_swaps.size(); i < ans; i++)
        P[i] = Q[i] = 0;
    for (int i = 0; i < req_swaps.size(); i++)
    {
        swap(S[X[i]],S[Y[i]]);
        pos[S[X[i]]] = X[i];
        pos[S[Y[i]]] = Y[i];
        P[i] = pos[req_swaps[i].first];
        Q[i] = pos[req_swaps[i].second];
        swap(S[P[i]],S[Q[i]]);
        pos[S[P[i]]] = P[i];
        pos[S[Q[i]]] = Q[i];
    }
    return ans;
}

///;gimme 1200 +constructive +greedy (nice one still)

Compilation message

sorting.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
sorting.cpp: In function 'int cnt_cyc(std::vector<int>)':
sorting.cpp:35:22: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   35 |     return cicli.size();
      |            ~~~~~~~~~~^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:71:32: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   71 |     for (int i = req_swaps.size(); i < ans; i++)
      |                  ~~~~~~~~~~~~~~^~
sorting.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < req_swaps.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 1 ms 712 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 776 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 2 ms 784 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 896 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 1 ms 712 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 776 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 2 ms 784 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 896 KB Output is correct
15 Correct 113 ms 25720 KB Output is correct
16 Correct 117 ms 26720 KB Output is correct
17 Correct 122 ms 28308 KB Output is correct
18 Correct 101 ms 28232 KB Output is correct
19 Correct 157 ms 28988 KB Output is correct
20 Correct 159 ms 30672 KB Output is correct
21 Correct 163 ms 29608 KB Output is correct
22 Correct 99 ms 19680 KB Output is correct
23 Correct 117 ms 29316 KB Output is correct
24 Correct 124 ms 28756 KB Output is correct
25 Correct 123 ms 27840 KB Output is correct
26 Correct 155 ms 27984 KB Output is correct
27 Correct 152 ms 28404 KB Output is correct
28 Correct 129 ms 27964 KB Output is correct
29 Correct 132 ms 22796 KB Output is correct
30 Correct 130 ms 27372 KB Output is correct
31 Correct 138 ms 23252 KB Output is correct
32 Correct 115 ms 28128 KB Output is correct
33 Correct 123 ms 28536 KB Output is correct
34 Correct 115 ms 22440 KB Output is correct
35 Correct 151 ms 28020 KB Output is correct
36 Correct 100 ms 27668 KB Output is correct
37 Correct 128 ms 33168 KB Output is correct
38 Correct 131 ms 30584 KB Output is correct
39 Correct 127 ms 31048 KB Output is correct