oj.uz

Submission #612439

# Submission time Handle Problem Language Result Execution time Memory
612439 2022-07-29T15:04:18 Z yuto1115 Sorting (IOI15_sorting) C++17
100 / 100
 452 ms 27820 KB 
#include "sorting.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n)-1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    int ok = n - 1, ng = -1;
    auto f = [&](int i) -> bool {
        vi to(n);
        iota(all(to), 0);
        vi rev(n);
        iota(all(rev), 0);
        rep(j, i) {
            swap(to[rev[x[j]]], to[rev[y[j]]]);
            swap(rev[x[j]], rev[y[j]]);
        }
        vvi ls;
        vb seen(n);
        rep(j, n) {
            if (seen[j]) continue;
            ls.pb({});
            int now = j;
            while (true) {
                seen[now] = true;
                ls.back().pb(now);
                int nx = s[rev[now]];
                if (seen[nx]) break;
                now = nx;
            }
        }
        return n - SZ(ls) <= i;
    };
    while (ok - ng > 1) {
        int mid = (ok + ng) / 2;
        if (f(mid)) ok = mid;
        else ng = mid;
    }
    int i = ok;
    vi to(n);
    iota(all(to), 0);
    vi rev(n);
    iota(all(rev), 0);
    rep(j, i) {
        swap(to[rev[x[j]]], to[rev[y[j]]]);
        swap(rev[x[j]], rev[y[j]]);
    }
    vvi ls;
    vb seen(n);
    rep(j, n) {
        if (seen[j]) continue;
        ls.pb({});
        int now = j;
        while (true) {
            seen[now] = true;
            ls.back().pb(now);
            int nx = s[rev[now]];
            if (seen[nx]) break;
            now = nx;
        }
    }
    vp ev;
    for (const vi &v: ls) {
        rep2(j, 1, SZ(v)) ev.eb(v[0], v[j]);
    }
    rep(j, i) {
        swap(rev[to[x[j]]], rev[to[y[j]]]);
        swap(to[x[j]], to[y[j]]);
        if (j < SZ(ev)) {
            p[j] = rev[ev[j].first];
            q[j] = rev[ev[j].second];
        } else {
            p[j] = q[j] = 0;
        }
    }
    return i;
}

Compilation message

sorting.cpp: In lambda function:
sorting.cpp:60:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   60 |             int now = j;
      |                       ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:90:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   90 |         int now = j;
      |                   ^
sorting.cpp:44:39: warning: unused parameter 'm' [-Wunused-parameter]
   44 | int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
      |                                   ~~~~^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 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 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 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 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 468 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 209 ms 10464 KB Output is correct
16 Correct 235 ms 20508 KB Output is correct
17 Correct 279 ms 22132 KB Output is correct
18 Correct 326 ms 26448 KB Output is correct
19 Correct 360 ms 26508 KB Output is correct
20 Correct 399 ms 26140 KB Output is correct
21 Correct 389 ms 25888 KB Output is correct
22 Correct 204 ms 15784 KB Output is correct
23 Correct 255 ms 22108 KB Output is correct
24 Correct 268 ms 22136 KB Output is correct
25 Correct 277 ms 22256 KB Output is correct
26 Correct 339 ms 27108 KB Output is correct
27 Correct 367 ms 25612 KB Output is correct
28 Correct 289 ms 22408 KB Output is correct
29 Correct 335 ms 22312 KB Output is correct
30 Correct 452 ms 27588 KB Output is correct
31 Correct 321 ms 23792 KB Output is correct
32 Correct 228 ms 21548 KB Output is correct
33 Correct 278 ms 21592 KB Output is correct
34 Correct 285 ms 21048 KB Output is correct
35 Correct 326 ms 26152 KB Output is correct
36 Correct 307 ms 27820 KB Output is correct
37 Correct 318 ms 22508 KB Output is correct
38 Correct 284 ms 21572 KB Output is correct
39 Correct 273 ms 21676 KB Output is correct