Submission #370812

#	Time	Username	Problem	Language	Result	Execution time	Memory
370812		sad	Cat (info1cup19_cat)	C++14	10 / 100	1099 ms	14052 KiB

cat

    /** 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 / 15
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 35