oj.uz

Submission #762929

# Submission time Handle Problem Language Result Execution time Memory
762929 2023-06-22T01:28:59 Z Trunkty Cat (info1cup19_cat) C++14
100 / 100
 416 ms 20728 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int t;
int n;
int arr[200005],pos[200005];

int val(int x){
    if(x>n/2){
        return n-x+1LL;
    }
    else{
        return x;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    for(int e=1;e<=t;e++){
        cin >> n;
        for(int i=1;i<=n;i++){
            cin >> arr[i];
        }
        bool bad = false;
        for(int i=1;i<=n/2;i++){
            if(arr[i]+arr[n-i+1LL]!=n+1LL){
                bad = true;
            }
        }
        if(bad){
            cout << -1 << "\n";
            continue;
        }
        for(int i=1;i<=n/2;i++){
            pos[val(arr[i])] = i;
        }
        vector<vector<int>> ans;
        for(int i=1;i<=n/2;i++){
            if(pos[i]!=i){
                if(arr[pos[i]]>n/2){
                    int x = pos[i];
                    arr[x] = n-arr[x]+1LL;
                    arr[i] = n-arr[i]+1LL;
                    swap(arr[i],arr[x]);
                    ans.push_back({i,n-x+1LL});
                    pos[val(arr[i])] = i;
                    pos[val(arr[x])] = x;
                }
                else{
                    int x = pos[i];
                    swap(arr[i],arr[x]);
                    ans.push_back({i,x});
                    pos[val(arr[i])] = i;
                    pos[val(arr[x])] = x;
                }
            }
        }
        int bef=-1;
        for(int i=1;i<=n/2;i++){
            if(arr[i]>n/2){
                if(bef==-1){
                    bef = i;
                }
                else{
                    ans.push_back({bef,i});
                    ans.push_back({bef,n-i+1LL});
                    bef = -1;
                }
            }
        }
        if(bef!=-1){
            cout << -1 << "\n";
        }
        else{
            cout << ans.size() << " " << ans.size() << "\n";
            for(vector<int> i:ans){
                cout << i[0] << " " << i[1] << "\n";
            }
        }
    }
    return 0;
}

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 516 KB Output is correct
2 Correct 15 ms 580 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 516 KB Output is correct
3 Correct 15 ms 580 KB Output is correct
4 Correct 17 ms 572 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 516 KB Output is correct
2 Correct 15 ms 580 KB Output is correct
3 Correct 416 ms 13428 KB Output is correct
4 Correct 340 ms 15804 KB Output is correct
5 Correct 397 ms 20348 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 516 KB Output is correct
3 Correct 15 ms 580 KB Output is correct
4 Correct 17 ms 572 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 416 ms 13428 KB Output is correct
8 Correct 340 ms 15804 KB Output is correct
9 Correct 397 ms 20348 KB Output is correct
10 Correct 357 ms 12876 KB Output is correct
11 Correct 337 ms 10096 KB Output is correct
12 Correct 341 ms 19244 KB Output is correct
13 Correct 370 ms 20728 KB Output is correct
14 Correct 370 ms 18644 KB Output is correct