oj.uz

Submission #783111

# Submission time Handle Problem Language Result Execution time Memory
783111 2023-07-14T15:33:44 Z Andrey Cat (info1cup19_cat) C++14
100 / 100
 463 ms 18660 KB 
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n,a,br = 0,y,b;
    cin >> n;
    vector<int> pos(n+1);
    vector<int> p(n+1);
    vector<pair<int,int>> ans(0);
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
        pos[p[i]] = i;
    }
    for(int i = 1; i <= n/2; i++) {
        if(pos[i] > pos[n-i+1]) {
            br++;
        }
        if(pos[i] != n-pos[n-i+1]+1) {
            cout << -1 << "\n";
            return;
        }
    }
    if(br%2) {
        cout << -1 << "\n";
        return;
    }
    br = 0;
    for(int i = 1; i <= n; i++) {
        y = i;
        while(p[y] != y && p[y] != n-y+1) {
            a = y;
            b = p[y];
            swap(p[a],p[b]);
            ans.push_back({a,b});
            swap(p[n-a+1],p[n-b+1]);
            br++;
        }
    }
    vector<int> idk(0);
    for(int i = 1; i <= n/2; i++) {
        if(p[i] == n-i+1) {
            br++;
            idk.push_back(i);
        }
    }
    for(int i = 0; i < idk.size(); i+=2) {
        ans.push_back({idk[i],n-idk[i+1]+1});
        ans.push_back({idk[i],idk[i+1]});
    }
    cout << br << " " << br << "\n";
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i].first << " " << ans[i].second << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 696 KB Output is correct
2 Correct 20 ms 804 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 18 ms 696 KB Output is correct
3 Correct 20 ms 804 KB Output is correct
4 Correct 21 ms 996 KB Output is correct
5 Correct 8 ms 576 KB Output is correct
6 Correct 7 ms 468 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 696 KB Output is correct
2 Correct 20 ms 804 KB Output is correct
3 Correct 413 ms 10232 KB Output is correct
4 Correct 383 ms 9572 KB Output is correct
5 Correct 405 ms 11588 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 18 ms 696 KB Output is correct
3 Correct 20 ms 804 KB Output is correct
4 Correct 21 ms 996 KB Output is correct
5 Correct 8 ms 576 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 413 ms 10232 KB Output is correct
8 Correct 383 ms 9572 KB Output is correct
9 Correct 405 ms 11588 KB Output is correct
10 Correct 412 ms 16512 KB Output is correct
11 Correct 356 ms 14692 KB Output is correct
12 Correct 415 ms 17324 KB Output is correct
13 Correct 463 ms 18660 KB Output is correct
14 Correct 420 ms 16376 KB Output is correct