oj.uz

Submission #572524

# Submission time Handle Problem Language Result Execution time Memory
572524 2022-06-04T15:53:23 Z MohamedFaresNebili Sorting (IOI15_sorting) C++14
24 / 100
 4 ms 852 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;
            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]]);

                int u = ind[pos[l]], v = pos[ind[u]];

                swap(s[u], s[v]);
                swap(pos[s[u]], pos[s[v]]);
            }
            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]]);

                int u = ind[pos[l]], v = pos[ind[u]];

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

                P[l] = u, Q[l] = v;
            }
            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 0 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 212 KB Output is correct

Subtask #2
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 0 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 212 KB Output is correct
8 Runtime error 1 ms 340 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

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

Subtask #4
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 0 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 212 KB Output is correct
8 Runtime error 1 ms 340 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -