제출 #1170775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170775		browntoad	Cat (info1cup19_cat)	C++20	39 / 100	1089 ms	15036 KiB

cat

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

#ifdef TOAD
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const ll maxn = 1e5+5;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;

signed main(){
	IOS();
	int T; cin>>T;
	while(T--){
		int n; cin>>n;
		vector<int> v(n), p(n);
		REP(i, n){
			cin>>v[i];
			v[i]--;
			p[v[i]] = i;
		}

		bool gg = false;
		bool oo = false;

		vector<int> specid;
		REP(i, n/2){
			if (v[i] < n/2){
				if (v[n-i-1] + v[i] != n-1){
					gg = 1;
					break;
				}
			}
			else{
				oo ^= 1;
				if (v[n-i-1] + v[i] != n-1){
					gg = 1;
					break;
				}
				swap(v[n-i-1], v[i]);
				p[v[i]] = i;
				specid.pb(i);
			}
		}
		// matching of specid, swap each swapping

		if (gg || oo){
			cout<<-1<<endl;
			continue;
		}
		vector<pii> ans;
		for(int i = 0; i < SZ(specid); i += 2){
			ans.pb({specid[i], n-specid[i+1]-1});
			swap(v[specid[i]], v[specid[i+1]]);
			p[v[specid[i]]] = specid[i];
			p[v[specid[i+1]]] = specid[i+1];
		}

		REP(i, n/2){
			if (v[i] == i) continue;
			int pp = p[i];
			ans.pb({i, pp});
			swap(v[i], v[pp]);
			p[v[i]] = i;
			p[v[pp]] = pp;
		}

		cout<<SZ(ans)<<' '<<SZ(ans)<<endl;
		for (auto pp:ans) cout<<pp.f+1<<' '<<pp.s+1<<endl;


	}
}

• Subtask 1: 5.25 / 15
• Subtask 2: 10 / 10
• Subtask 3: 8.75 / 25
• Subtask 4: 15 / 15
• Subtask 5: 0 / 35