oj.uz

Submission #572519

# Submission time Handle Problem Language Result Execution time Memory
572519 2022-06-04T15:35:12 Z MohamedFaresNebili Sorting (IOI15_sorting) C++14
74 / 100
 1000 ms 28128 KB 
#include <bits/stdc++.h>
#include "sorting.h"
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define all(x) (x).begin(), (x).end()

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        bool can(int N, int S[], int M, int X[], int Y[]) {
            int s[N], x[M], y[M];
            int res[N], pos[N], ind[N];
            for(int l = 0; l < N; l++) s[l] = S[l];
            for(int l = 0; l < M; l++)
                x[l] = X[l], y[l] = Y[l];
            for(int l = 0; l < N; l++) {
                res[l] = l; pos[s[l]] = l;
            }
            for(int l = 0; l < M; l++) {
                int i = x[l], j = y[l];
                swap(res[i], res[j]);
            }
            for(int l = 0; l < N; l++)
                ind[res[l]] = l;
            unordered_map<int, bool> se;
            for(int l = 0; l < N; l++) {
                if(s[l] == ind[l]) continue;
                se[l] = 1;
            }
            for(int l = 0; l < M; l++) {
                int i = x[l], j = y[l];
                swap(s[i], s[j]);
                swap(pos[s[i]], pos[s[j]]);
                i = ind[i], j = ind[j];
                swap(res[i], res[j]);
                swap(ind[res[i]], ind[res[j]]);

                if(se.count(x[l])) se.erase(x[l]);
                if(se.count(y[l])) se.erase(y[l]);
                if(s[x[l]] != ind[x[l]]) se[x[l]] = 1;
                if(s[y[l]] != ind[y[l]]) se[y[l]] = 1;

                int u = 0, v = 0;
                if(se.size() != 0) {
                    auto it = se.begin();
                    u = it->first;
                    v = pos[ind[it->first]];
                }

                swap(s[u], s[v]);
                swap(pos[s[u]], pos[s[v]]);

                if(se.count(u)) se.erase(u);
                if(se.count(v)) se.erase(v);

                if(s[u] != ind[u]) se[u] = 1;
                if(s[v] != ind[v]) se[v] = 1;
            }
            for(int l = 0; l < N - 1; l++)
                if(s[l] > s[l + 1]) return 0;
            return 1;
        }

        int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
            int lo = 0, hi = M;
            while(lo <= hi) {
                int md = (lo + hi) / 2;
                if(can(N, S, md, X, Y)) {
                    M = md; hi = md - 1;
                }
                else lo = md + 1;
            }
            int res[N], pos[N], ind[N];
            for(int l = 0; l < N; l++) {
                res[l] = l; pos[S[l]] = l;
            }
            for(int l = 0; l < M; l++) {
                int i = X[l], j = Y[l];
                swap(res[i], res[j]);
            }
            for(int l = 0; l < N; l++)
                ind[res[l]] = l;
            unordered_map<int, bool> se;
            for(int l = 0; l < N; l++) {
                if(S[l] == ind[l]) continue;
                se[l] = 1;
            }
            for(int l = 0; l < M; l++) {
                int i = X[l], j = Y[l];
                swap(S[i], S[j]);
                swap(pos[S[i]], pos[S[j]]);
                i = ind[i], j = ind[j];
                swap(res[i], res[j]);
                swap(ind[res[i]], ind[res[j]]);

                if(se.count(X[l])) se.erase(X[l]);
                if(se.count(Y[l])) se.erase(Y[l]);

                if(S[X[l]] != ind[X[l]]) se[X[l]];
                if(S[Y[l]] != ind[Y[l]]) se[Y[l]];

                int u = 0, v = 0;
                if(se.size() != 0) {
                    auto it = se.begin();
                    u = it->first, v = pos[ind[it->first]];
                }

                swap(S[u], S[v]);
                swap(pos[S[u]], pos[S[v]]);

                P[l] = u, Q[l] = v;

                if(se.count(u)) se.erase(u);
                if(se.count(v)) se.erase(v);

                if(S[u] != ind[u]) se[u] = 1;
                if(S[v] != ind[v]) se[v] = 1;
            }
            return M;
        }

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 308 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 4 ms 596 KB Output is correct
22 Correct 4 ms 612 KB Output is correct
23 Correct 4 ms 596 KB Output is correct
24 Correct 3 ms 596 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 3 ms 596 KB Output is correct
27 Correct 3 ms 568 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Output is correct
2 Correct 8 ms 596 KB Output is correct
3 Correct 9 ms 596 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 568 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 9 ms 564 KB Output is correct
9 Correct 9 ms 560 KB Output is correct
10 Correct 9 ms 580 KB Output is correct
11 Correct 8 ms 576 KB Output is correct
12 Correct 7 ms 564 KB Output is correct
13 Correct 9 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Execution timed out 1020 ms 28128 KB Time limit exceeded
16 Halted 0 ms 0 KB -