oj.uz

Submission #697170

# Submission time Handle Problem Language Result Execution time Memory
697170 2023-02-08T17:13:58 Z Danilo21 Sorting (IOI15_sorting) C++14
100 / 100
 339 ms 28164 KB 
#include <bits/stdc++.h>
#include "sorting.h"

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "Yes" << en
#define no cout << "No" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

const ll LINF = 1e18;
const int mxN = 1e6+10, INF = 2e9;
int n, m, a[mxN], idx[mxN], *s, *x, *y;
vector<vector<int> > cycles;
bool vis[mxN];

void dfs(int i){

    vis[i] = 1;
    cycles.back().pb(a[i]);
    if (!vis[a[i]]) dfs(a[i]);
}

bool Check(int k){

    memset(vis, 0, sizeof(vis));
    cycles.clear();
    for (int i = 0; i < n; i++)
        a[i] = s[i];
    for (int i = 0; i < k; i++)
        swap(a[x[i]], a[y[i]]);
    for (int i = 0; i < n; i++){
        if (!vis[i]){
            cycles.pb({});
            dfs(i);
        }
    }
    return n-cycles.size() <= k;
}

void Swap(int i, int j){
    swap(idx[s[i]], idx[s[j]]);
    swap(s[i], s[j]);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N; m = M;
    s = S; x = X; y = Y;
    int l = 0, r = m-1, ans = m;
    while (l <= r){
        int k = (l + r + 1)>>1;
        if (Check(k)){
            ans = k;
            r = k - 1;
        }
        else l = k + 1;
    }
    Check(ans);
    vector<array<int, 2> > v;
    for (auto c : cycles)
        for (int i = 0; i < c.size()-1; i++)
            v.pb({c[i], c[i+1]});
    for (int i = 0; i < n; i++)
        idx[s[i]] = i;
    for (int i = 0; i < ans; i++){
        Swap(x[i], y[i]);
        if (i < v.size()){
            P[i] = idx[v[i][0]];
            Q[i] = idx[v[i][1]];
        }
        else P[i] = Q[i] = 0;
        Swap(P[i], Q[i]);
    }
	return ans;
}

Compilation message

sorting.cpp: In function 'bool Check(int)':
sorting.cpp:60:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |     return n-cycles.size() <= k;
      |            ~~~~~~~~~~~~~~~~^~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int i = 0; i < c.size()-1; i++)
      |                         ~~^~~~~~~~~~~~
sorting.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         if (i < v.size()){
      |             ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1220 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1224 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 1 ms 1236 KB Output is correct
14 Correct 1 ms 1236 KB Output is correct
15 Correct 1 ms 1228 KB Output is correct
16 Correct 1 ms 1236 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 2 ms 1236 KB Output is correct
19 Correct 2 ms 1236 KB Output is correct
20 Correct 1 ms 1216 KB Output is correct
21 Correct 3 ms 1492 KB Output is correct
22 Correct 2 ms 1492 KB Output is correct
23 Correct 2 ms 1492 KB Output is correct
24 Correct 2 ms 1484 KB Output is correct
25 Correct 3 ms 1484 KB Output is correct
26 Correct 2 ms 1492 KB Output is correct
27 Correct 2 ms 1492 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 2 ms 1432 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 5 ms 1484 KB Output is correct
5 Correct 4 ms 1456 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 2 ms 1492 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 2 ms 1492 KB Output is correct
12 Correct 3 ms 1492 KB Output is correct
13 Correct 3 ms 1492 KB Output is correct
14 Correct 3 ms 1488 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 2 ms 1432 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 5 ms 1484 KB Output is correct
5 Correct 4 ms 1456 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 2 ms 1492 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 2 ms 1492 KB Output is correct
12 Correct 3 ms 1492 KB Output is correct
13 Correct 3 ms 1492 KB Output is correct
14 Correct 3 ms 1488 KB Output is correct
15 Correct 138 ms 19484 KB Output is correct
16 Correct 158 ms 21948 KB Output is correct
17 Correct 171 ms 21160 KB Output is correct
18 Correct 203 ms 25900 KB Output is correct
19 Correct 305 ms 26736 KB Output is correct
20 Correct 267 ms 27440 KB Output is correct
21 Correct 268 ms 27380 KB Output is correct
22 Correct 131 ms 15960 KB Output is correct
23 Correct 166 ms 21532 KB Output is correct
24 Correct 184 ms 21440 KB Output is correct
25 Correct 166 ms 23488 KB Output is correct
26 Correct 339 ms 28136 KB Output is correct
27 Correct 261 ms 28164 KB Output is correct
28 Correct 220 ms 23788 KB Output is correct
29 Correct 227 ms 22604 KB Output is correct
30 Correct 247 ms 27840 KB Output is correct
31 Correct 211 ms 23716 KB Output is correct
32 Correct 148 ms 21028 KB Output is correct
33 Correct 160 ms 21824 KB Output is correct
34 Correct 158 ms 21152 KB Output is correct
35 Correct 245 ms 26308 KB Output is correct
36 Correct 205 ms 27684 KB Output is correct
37 Correct 179 ms 26340 KB Output is correct
38 Correct 165 ms 25224 KB Output is correct
39 Correct 166 ms 25636 KB Output is correct