oj.uz

Submission #251980

# Submission time Handle Problem Language Result Execution time Memory
251980 2020-07-23T11:54:33 Z paradox Sorting (IOI15_sorting) C++17
100 / 100
 375 ms 30496 KB 
#include "sorting.h"

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define vi vector<int>
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)


typedef long long ll;
typedef short inth;
 
const int K = 6e5 + 7;
const int MOD = 1e9 + 7;
const ll INF = 1e16 + 17;

int m, n;
pii query[K], ans[K];

pii temp[K];

int pos[K];

bool check(int t, int S[]) {
    int out[n], in[n];
    for (int i = 0; i < n; ++i)
        out[i] = in[i] = S[i];

    for (int id = 0; id < t; ++id) {
        int i = query[id].fi, j = query[id].se;
        swap(out[i], out[j]);
    }

    bool us[n];
    memset(us, false, sizeof us);

    int cnt = 0;

    for (int i = 0; i < n; ++i) {
        if (us[i])
            continue;
        
        vi ord;
        int v = out[i];
        while (v != i) {
            ord.pb(v);
            us[v] = true;
            v = out[v];
        }
        ord.pb(v);
        us[v] = true;

        for (int j = sz(ord) - 1; j > 0; --j)
            temp[cnt++] = mp(ord[0], ord[j]);
    }

    if (cnt > t)
        return false;
    
    for (int i = 0; i < n; ++i)
        pos[in[i]] = i;

    for (int id = 0; id < cnt; ++id) {

        int i = query[id].fi, j = query[id].se;
        swap(in[i], in[j]);
        pos[in[i]] = i;
        pos[in[j]] = j;

        i = pos[temp[id].fi]; j = pos[temp[id].se];
        ans[id] = mp(i, j);
        swap(in[i], in[j]);
        pos[in[i]] = i;
        pos[in[j]] = j;
    }

    while (cnt < t)
        ans[cnt++] = mp(0, 0);

    return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int l = -1, r = M;

    m = M; n = N;
    for (int i = 0; i < m; ++i)
        query[i] = mp(X[i], Y[i]);

    while (r - l > 1) {
        int m = (l + r) >> 1;
        if (check(m, S)) {
            r = m;
        } else {
            l = m;
        }
    }
    check(r, S);
    for (int i = 0; i < r; ++i) {
        P[i] = ans[i].fi;
        Q[i] = ans[i].se;
    }
    return r;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:119:13: warning: declaration of 'm' shadows a global declaration [-Wshadow]
         int m = (l + r) >> 1;
             ^
sorting.cpp:45:5: note: shadowed declaration is here
 int m, n;
     ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 260 ms 19524 KB Output is correct
16 Correct 335 ms 27356 KB Output is correct
17 Correct 325 ms 29408 KB Output is correct
18 Correct 233 ms 24412 KB Output is correct
19 Correct 319 ms 27968 KB Output is correct
20 Correct 345 ms 28236 KB Output is correct
21 Correct 329 ms 28404 KB Output is correct
22 Correct 275 ms 24288 KB Output is correct
23 Correct 312 ms 30496 KB Output is correct
24 Correct 356 ms 30068 KB Output is correct
25 Correct 373 ms 29752 KB Output is correct
26 Correct 328 ms 27384 KB Output is correct
27 Correct 295 ms 26232 KB Output is correct
28 Correct 341 ms 28952 KB Output is correct
29 Correct 369 ms 28080 KB Output is correct
30 Correct 276 ms 25468 KB Output is correct
31 Correct 375 ms 28792 KB Output is correct
32 Correct 310 ms 28872 KB Output is correct
33 Correct 333 ms 30020 KB Output is correct
34 Correct 300 ms 29176 KB Output is correct
35 Correct 334 ms 26880 KB Output is correct
36 Correct 204 ms 23928 KB Output is correct
37 Correct 334 ms 30256 KB Output is correct
38 Correct 329 ms 28788 KB Output is correct
39 Correct 351 ms 28968 KB Output is correct