oj.uz

Submission #793861

# Submission time Handle Problem Language Result Execution time Memory
793861 2023-07-26T07:37:35 Z PixelCat Sorting (IOI15_sorting) C++14
54 / 100
 8 ms 576 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) {
            if(sz(ops) == lim) return false;
            // For(j, 0, n - 1) cerr << tmp[j] << " ";
            // cerr << "--> ";
            // cerr << tmp[i] << ", " << tmp[tmp[i]] << "\n";
            ops.eb(tmp[i], tmp[tmp[i]]);
            swap(tmp[i], tmp[tmp[i]]);
        }
    }
    return true;
}

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[]) {
    For(i, 0, N - 1) {
        val[i] = S[i];
        pos[val[i]] = i;
    }
    // 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;
            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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 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 1 ms 340 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 316 KB Output is correct

Subtask #3
16.0 / 16.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 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 1 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 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 1 ms 340 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 316 KB Output is correct
13 Correct 0 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 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 1 ms 572 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 2 ms 468 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Output is correct
2 Correct 8 ms 576 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Incorrect 1 ms 444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Output is correct
2 Correct 8 ms 576 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Incorrect 1 ms 444 KB Output isn't correct
5 Halted 0 ms 0 KB -