oj.uz

Submission #572521

# Submission time Handle Problem Language Result Execution time Memory
572521 2022-06-04T15:43:00 Z MohamedFaresNebili Sorting (IOI15_sorting) C++14
74 / 100
 1000 ms 20544 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include "sorting.h"
 
        using namespace std;
 
        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()
 
        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 0 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 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 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 212 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 340 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 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
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 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 212 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 340 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 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 4 ms 468 KB Output is correct
22 Correct 4 ms 500 KB Output is correct
23 Correct 4 ms 468 KB Output is correct
24 Correct 4 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 3 ms 468 KB Output is correct
27 Correct 4 ms 468 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 496 KB Output is correct
2 Correct 9 ms 468 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 5 ms 500 KB Output is correct
7 Correct 7 ms 468 KB Output is correct
8 Correct 11 ms 500 KB Output is correct
9 Correct 10 ms 504 KB Output is correct
10 Correct 10 ms 468 KB Output is correct
11 Correct 8 ms 520 KB Output is correct
12 Correct 7 ms 512 KB Output is correct
13 Correct 10 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Execution timed out 1095 ms 20544 KB Time limit exceeded
16 Halted 0 ms 0 KB -