oj.uz

Submission #572537

# Submission time Handle Problem Language Result Execution time Memory
572537 2022-06-04T16:28:21 Z MohamedFaresNebili Sorting (IOI15_sorting) C++14
0 / 100
 1 ms 340 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;
 
        vector<ii> ans, ve;
        bool can(int N, int S[], int M, int X[], int Y[]) {
            ve.clear();
            int s[N], pos[N], res[N], arr[N], a[N], x[M], y[M];
            for(int l = 0; l < N; l++) {
                res[l] = l, arr[l] = l; a[l] = l;
                s[l] = S[l]; pos[s[l]] = l;
            }
            for(int l = 0; l < M; l++) {
                x[l] = X[l], y[l] = Y[l];
                swap(res[x[l]], res[y[l]]);
            }
            int c = 0;
            for(int l = 0; l < N; l++) {
                if(res[l] == pos[l]) continue;
                int i = X[c], j = Y[c];
                swap(arr[i], arr[j]);
                swap(a[arr[i]], a[arr[j]]);
 
                ve.pb({a[pos[l]], a[res[l]]});
                swap(pos[l], pos[s[res[l]]]);
                swap(s[pos[l]], s[res[l]]);
                c++;
            }
            if(c > M) return 0;
            for(int l = c; l < M; l++) ve.pb({0, 0});
            return 1;
        }

		int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
            int lo = 0, hi = N - 1; M = N; ans.clear();
            while(lo <= hi) {
                int md = (lo + hi) / 2;
                if(can(N, S, md, X, Y)) {
                    M = md; hi = md - 1;
                    ans.assign(all(ve));
                }
                else lo = md + 1;
            }
            int l = 0;
            for(auto u : ans) P[l] = u.ff, Q[l++] = u.ss;
            return M;
        }

Subtask #1
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 1 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
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 1 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
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 1 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -