oj.uz

Submission #794100

# Submission time Handle Problem Language Result Execution time Memory
794100 2023-07-26T09:21:53 Z PixelCat Sorting (IOI15_sorting) C++14
74 / 100
 1000 ms 24008 KB 
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "sorting.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;

int val[MAXN + 10];
int pos[MAXN + 10];

int tmp[MAXN + 10];
bool check(int n, int lim, vector<pii> &ops) {
    For(i, 0, n - 1) tmp[i] = val[i];
    ops.clear();
    For(i, 0, n - 1) {
        while(tmp[i] != i) {
            ops.eb(tmp[i], tmp[tmp[i]]);
            swap(tmp[i], tmp[tmp[i]]);
        }
    }
    return sz(ops) <= lim;
}

void out(int n) {
    cerr << "out:\n";
    cerr << "  "; For(i, 0, n - 1) cerr << val[i] << " \n"[i == n - 1];
    cerr << "  "; For(i, 0, n - 1) cerr << pos[i] << " \n"[i == n - 1];
}

int32_t findSwapPairs(int32_t N, int32_t S[], int32_t M, int32_t X[], int32_t Y[], int32_t P[], int32_t Q[]) {
    bool pote = true;
    For(i, 0, N - 1) {
        val[i] = S[i];
        pos[val[i]] = i;
        if(S[i] != i) pote = false;
    }
    if(pote) return 0;
    // out(N);
    For(i, 0, M - 1) {
        int p1 = X[i], p2 = Y[i];
        swap(pos[val[p1]], pos[val[p2]]);
        swap(val[p1], val[p2]);
        // For(j, 0, N - 1) cerr << val[j] << " \n"[j == N - 1];
        vector<pii> op;
        if(check(N, i + 1, op)) {
            For(j, sz(op), i) P[j] = Q[j] = 0;
            assert(sz(op) >= i);
            Forr(j, i, 0) {
                if(j < sz(op)) {
                    int v1 = op[j].F;
                    int v2 = op[j].S;
                    P[j] = (int32_t)pos[v1];
                    Q[j] = (int32_t)pos[v2];
                    swap(val[pos[v1]], val[pos[v2]]);
                    swap(pos[v1], pos[v2]);
                    // out(N);
                }
                p1 = X[j]; p2 = Y[j];
                swap(pos[val[p1]], pos[val[p2]]);
                swap(val[p1], val[p2]);
                // out(N);
            }
            return (int32_t)(i + 1);
        }
        // cerr << "\n";
    }
    assert(false);
    return 0;
}

/*

30421
10423
10243

*/

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 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 0 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 320 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 0 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 320 KB Output is correct
13 Correct 1 ms 304 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 3 ms 576 KB Output is correct
22 Correct 2 ms 448 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 576 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 2 ms 564 KB Output is correct
27 Correct 2 ms 468 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB Output is correct
2 Correct 19 ms 556 KB Output is correct
3 Correct 14 ms 540 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 452 KB Output is correct
7 Correct 6 ms 544 KB Output is correct
8 Correct 22 ms 468 KB Output is correct
9 Correct 20 ms 540 KB Output is correct
10 Correct 22 ms 468 KB Output is correct
11 Correct 22 ms 548 KB Output is correct
12 Correct 6 ms 524 KB Output is correct
13 Correct 14 ms 468 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 16 ms 468 KB Output is correct
2 Correct 19 ms 556 KB Output is correct
3 Correct 14 ms 540 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 452 KB Output is correct
7 Correct 6 ms 544 KB Output is correct
8 Correct 22 ms 468 KB Output is correct
9 Correct 20 ms 540 KB Output is correct
10 Correct 22 ms 468 KB Output is correct
11 Correct 22 ms 548 KB Output is correct
12 Correct 6 ms 524 KB Output is correct
13 Correct 14 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Execution timed out 1047 ms 24008 KB Time limit exceeded
16 Halted 0 ms 0 KB -