oj.uz

Submission #370812

# Submission time Handle Problem Language Result Execution time Memory
370812 2021-02-24T17:01:23 Z sad Cat (info1cup19_cat) C++14
10 / 100
 1000 ms 14052 KB 
    /** made by amunduzbaev **/
    #include <bits/stdc++.h>
    using namespace std;

    #define ff first
    #define ss second
    #define pb push_back
    #define mp make_pair
    #define ub upper_bound
    #define lb lower_bound
    #define sz(x) (int)x.size()
    #define all(x) x.begin(), x.end()
    #define rall(x) x.rbegin(),x.rend()
    #define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #define int long long
    typedef long long ll;
    typedef long double ld;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    typedef vector<ll> vll;
    typedef vector<int> vii;
    typedef vector<pll> vpll;
    typedef vector<pii> vpii;
    template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
    template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

    const int N = 2e5+5;
    const int mod = 1e9+7;
    const ll inf = 1e18;
    const ld Pi = acos(-1);

    #define MULTI 1

    int n, m, k, ans, res, a[N], pos[N];

    /*

    1
    6
    2 6 4 3 1 5

    */

    void solve(int t_case){
    	//memset(pos, 0, sizeof pos);
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i], pos[a[i]] = i;
    	//for(int i=1;i<=n;i++) cout<<pos[i]<<" ";
    	//cout<<"\n";

    	//for(int i=1;i<=n;i++) assert(pos[i] != 0);

    	vpii res;
    	for(int i=1;i<=n;i++){
    		if(a[i] != i){
    			int l = i, r = pos[i];
    			assert(l != r);
    			res.pb({l, r});
    			swap(a[l], a[r]);
    			swap(pos[a[l]], pos[a[r]]);
    			if(n-l+1 != r){
    				l = n-l+1, r = n-r+1;
    				assert(l != r);
    				swap(a[l], a[r]);
    				swap(pos[a[l]], pos[a[r]]);
    			}
    		}
    	}
    	for(int i=1;i<=n;i++){
    		if(a[i] != i){
    			cout<<-1<<"\n";
    			return;
    		}
    	}

    	cout<<0<<" "<<sz(res)<<"\n";
    	for(auto x:res) cout<<x.ff<<" "<<x.ss<<"\n";
    }

    signed main(){

    	if(!MULTI) {
    		solve(1);
    	} else {
    		int t; cin>>t;
    		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
    	}
    	return 0;
    }

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 364 KB Wrong answer

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 620 KB Output is correct
2 Correct 54 ms 620 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 364 KB Wrong answer

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 620 KB Output is correct
2 Correct 54 ms 620 KB Output is correct
3 Execution timed out 1099 ms 14052 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 364 KB Wrong answer