oj.uz

Submission #861279

# Submission time Handle Problem Language Result Execution time Memory
861279 2023-10-15T19:13:43 Z Ahmed57 Cat (info1cup19_cat) C++17
36.25 / 100
 431 ms 23548 KB 
#include <bits/stdc++.h>

using namespace std;
vector<pair<int,int>> con;
bool vis[200001];int arr[200001];
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t;cin>>t;
    z:while(t--){
        int n;cin>>n;
        for(int i = 1;i<=n;i++)vis[i] = 0;
        con.clear();
        int pos[n+1];
        for(int i = 1;i<=n;i++){
            cin>>arr[i];pos[arr[i]] = i;
        }
        int g = 0;int lol = 0;
        for(int i = 1;i<=n/2;i++){
            if(arr[i]!=i)g++;
            if(n-arr[i]+1!=arr[n-i+1]){
                cout<<-1<<endl;
                goto z;
            }if(arr[i]>n/2){
                lol++;
            }
        }
        if(lol&1){
            cout<<-1<<endl;
            goto z;
        }
        for(int i = 1;i<=n/2;i++){
            if(!vis[i]){
                int st = i;
                vis[i] = 1;
                int e = arr[i];
                while(vis[e]==0){
                    vis[e] = 1;
                    con.push_back({e,i});
                    e = arr[e];
                }
            }
        }
        cout<<con.size()<<" "<<con.size()<<"\n";
        for(auto i:con)cout<<i.first<<" "<<i.second<<"\n";
    }
}

Compilation message

cat.cpp: In function 'int main()':
cat.cpp:33:21: warning: unused variable 'st' [-Wunused-variable]
   33 |                 int st = i;
      |                     ^~
cat.cpp:13:13: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
   13 |         int pos[n+1];
      |             ^~~

Subtask #1
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Correctly distinguished between possibility and impossibility

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 604 KB Output is correct
2 Correct 14 ms 604 KB Output is correct

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Correctly distinguished between possibility and impossibility
2 Correct 18 ms 604 KB Output is correct
3 Correct 14 ms 604 KB Output is correct
4 Correct 19 ms 860 KB Correctly distinguished between possibility and impossibility
5 Correct 8 ms 600 KB Correctly distinguished between possibility and impossibility
6 Correct 6 ms 604 KB Correctly distinguished between possibility and impossibility

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 604 KB Output is correct
2 Correct 14 ms 604 KB Output is correct
3 Correct 282 ms 10448 KB Output is correct
4 Correct 268 ms 9932 KB Output is correct
5 Correct 291 ms 12408 KB Output is correct

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Correctly distinguished between possibility and impossibility
2 Correct 18 ms 604 KB Output is correct
3 Correct 14 ms 604 KB Output is correct
4 Correct 19 ms 860 KB Correctly distinguished between possibility and impossibility
5 Correct 8 ms 600 KB Correctly distinguished between possibility and impossibility
6 Correct 6 ms 604 KB Correctly distinguished between possibility and impossibility
7 Correct 282 ms 10448 KB Output is correct
8 Correct 268 ms 9932 KB Output is correct
9 Correct 291 ms 12408 KB Output is correct
10 Correct 407 ms 18256 KB Correctly distinguished between possibility and impossibility
11 Correct 357 ms 14940 KB Correctly distinguished between possibility and impossibility
12 Correct 388 ms 20552 KB Correctly distinguished between possibility and impossibility
13 Correct 431 ms 23548 KB Correctly distinguished between possibility and impossibility
14 Correct 376 ms 19768 KB Correctly distinguished between possibility and impossibility