oj.uz

Submission #950427

# Submission time Handle Problem Language Result Execution time Memory
950427 2024-03-20T10:03:08 Z Pring Cat (info1cup19_cat) C++17
51.25 / 100
 348 ms 30616 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 200005;
int N, p[MXN];
int n;
vector<pii> ans;

void SORT() {
    FOR(i, 1, n + 1) {
        if (p[i] == i) continue;
        while (p[i] != i) {
            ans.emplace_back(i, p[i]);
            swap(p[i], p[p[i]]);
        }
    }
}

void COUT() {
    cout << ans.size() << ' ' << ans.size() << '\n';
    for (auto &i : ans) cout << i.fs << ' ' << i.sc << '\n';
}

namespace SB24 {
 
    void solve() {
        SORT();
        COUT();
    }
}

void solve() {
    vector<int> w;
    FOR(i, 1, n + 1) {
        if (p[i] > p[N - i + 1]) {
            w.push_back(i);
            swap(p[i], p[N - i + 1]);
        }
    }
    // cout << "w: ";
    // for (auto &i : w) cout << i << ' ';
    // cout << endl;
    if (w.size() % 2) {
        cout << -1 << '\n';
        return;
    }
    for (int i = 0; i < w.size(); i += 2) {
        ans.emplace_back(w[i], N - w[i + 1] + 1);
        swap(p[w[i]], p[w[i + 1]]);
    }
    SORT();
    COUT();
}

void miku() {
    cin >> N;
    n = N / 2;
    FOR(i, 1, N + 1) cin >> p[i];
    FOR(i, 1, n + 1) {
        if (p[i] + p[N - i + 1] != N + 1) {
            cout << -1 << '\n';
            return;
        }
    }
    if (*max_element(p + 1, p + n + 1) <= n) {
        SB24::solve();
        return;
    }
    solve();
}

void RESET() {
    ans.clear();
}
int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int t;
    cin >> t;
    while (t--) {
        miku();
        RESET();
    }
    return 0;
}

Compilation message

cat.cpp: In function 'void solve()':
cat.cpp:54:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < w.size(); i += 2) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.25 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 344 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 980 KB Output is correct
2 Correct 12 ms 1368 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 344 KB Valid reconstruction
2 Correct 18 ms 980 KB Output is correct
3 Correct 12 ms 1368 KB Output is correct
4 Partially correct 16 ms 1116 KB Valid reconstruction
5 Partially correct 8 ms 600 KB Valid reconstruction
6 Partially correct 5 ms 604 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 980 KB Output is correct
2 Correct 12 ms 1368 KB Output is correct
3 Correct 282 ms 25804 KB Output is correct
4 Correct 292 ms 25556 KB Output is correct
5 Correct 301 ms 27588 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 344 KB Valid reconstruction
2 Correct 18 ms 980 KB Output is correct
3 Correct 12 ms 1368 KB Output is correct
4 Partially correct 16 ms 1116 KB Valid reconstruction
5 Partially correct 8 ms 600 KB Valid reconstruction
6 Partially correct 5 ms 604 KB Valid reconstruction
7 Correct 282 ms 25804 KB Output is correct
8 Correct 292 ms 25556 KB Output is correct
9 Correct 301 ms 27588 KB Output is correct
10 Partially correct 328 ms 25172 KB Valid reconstruction
11 Partially correct 304 ms 23636 KB Valid reconstruction
12 Partially correct 318 ms 29248 KB Valid reconstruction
13 Partially correct 348 ms 30616 KB Valid reconstruction
14 Partially correct 325 ms 29148 KB Valid reconstruction