oj.uz

Submission #432817

# Submission time Handle Problem Language Result Execution time Memory
432817 2021-06-18T13:31:08 Z 2qbingxuan Sorting (IOI15_sorting) C++17
100 / 100
 545 ms 27284 KB 
#include "sorting.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(a...) qqbx(#a, a)
#define pary(a...) danb(#a, a)
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\e[1;32m(" << s << ") = ("), ..., (std::cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    if (is_sorted(S, S+N)) return 0;
    vector<pair<int,int>> best(M, pair<int,int>(-1, -1));

    auto go = [&](int R) {
        vector<int> targ(N);
        for (int i = 0; i < N; i++) targ[i] = i;
        for (int i = R-1; i >= 0; i--)
            swap(targ[X[i]], targ[Y[i]]);

        vector<int> s(S, S+N);
        vector<int> pos(N);
        for (int i = 0; i < N; i++)
            pos[s[i]] = i;
        vector<pair<int,int>> ans;
        for (int i = 0, it = 0; i < R; i++) {
            {
                int a = X[i], b = Y[i];
                swap(targ[a], targ[b]);
                swap(pos[s[a]], pos[s[b]]);
                swap(s[a], s[b]);
            }
            {
                while (it < N && pos[it] == pos[targ[pos[it]]]) ++it;
                if (it == N) {
                    ans.emplace_back(0, 0);
                } else {
                    ;
                    int a = pos[it];
                    int b = pos[targ[a]];
                    swap(pos[s[a]], pos[s[b]]);
                    swap(s[a], s[b]);
                    ans.emplace_back(a, b);
                }
            }
        }
        // pary(all(s));
        if (is_sorted(all(s))) {
            if (best.size() > ans.size())
                best = ans;
            return true;
        } else {
            return false;
        }
    };

    int ans = 0;
    for (int s = 1<<20; s; s>>=1)
        if (ans + s <= M && !go(ans + s))
            ans += s;
    ++ans;
    go(ans);
    for (size_t i = 0; i < best.size(); i++)
        tie(P[i], Q[i]) = best[i];
    return best.size();
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:80:21: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   80 |     return best.size();
      |            ~~~~~~~~~^~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 2 ms 736 KB Output is correct
23 Correct 2 ms 716 KB Output is correct
24 Correct 2 ms 696 KB Output is correct
25 Correct 2 ms 716 KB Output is correct
26 Correct 2 ms 716 KB Output is correct
27 Correct 2 ms 716 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 3 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 410 ms 24396 KB Output is correct
16 Correct 442 ms 24908 KB Output is correct
17 Correct 487 ms 26056 KB Output is correct
18 Correct 47 ms 13380 KB Output is correct
19 Correct 314 ms 25884 KB Output is correct
20 Correct 344 ms 26472 KB Output is correct
21 Correct 341 ms 26620 KB Output is correct
22 Correct 416 ms 21436 KB Output is correct
23 Correct 479 ms 26892 KB Output is correct
24 Correct 507 ms 26572 KB Output is correct
25 Correct 503 ms 26244 KB Output is correct
26 Correct 342 ms 26556 KB Output is correct
27 Correct 311 ms 25940 KB Output is correct
28 Correct 486 ms 26584 KB Output is correct
29 Correct 475 ms 26164 KB Output is correct
30 Correct 207 ms 25808 KB Output is correct
31 Correct 456 ms 26708 KB Output is correct
32 Correct 457 ms 26060 KB Output is correct
33 Correct 502 ms 26480 KB Output is correct
34 Correct 459 ms 26424 KB Output is correct
35 Correct 320 ms 25620 KB Output is correct
36 Correct 98 ms 25496 KB Output is correct
37 Correct 545 ms 27284 KB Output is correct
38 Correct 495 ms 26308 KB Output is correct
39 Correct 500 ms 26484 KB Output is correct