Submission #315286

#	Time	Username	Problem	Language	Result	Execution time	Memory
315286		Kevin_Zhang_TW	Cat (info1cup19_cat)	C++17	25 / 100	566 ms	16988 KiB

cat

#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
#undef KEV
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 3000010;
int per[MAX_N], n, pos[MAX_N], ma[MAX_N], cp[MAX_N];
void fail() {
	puts("-1"), exit(0);
}
void sw(int a, int b) {
	swap(per[a], per[b]);
	swap(pos[per[a]], pos[per[b]]);
}
int rev(int i) {
	return n - i + 1;
}
vector< pair<int,int> > res;
bool part() {
	vector<int> L, R;
	int m = n / 2;
	for (int i = 1;i <= m;++i)
		if (per[i] > m)
			L.pb(i);
	for (int i = m+1;i <= n;++i)
		if (per[i] <= m)
			R.pb(i);
 
	assert(L.size() == R.size());
 
	reverse(AI(R));
	m = L.size();
	if (m&1) return false;
	for (int i = 0;i < m;++i)
		if (L[i] != rev(R[i])) 
			return false;
	for (int i = 1;i <= n;++i)
		cp[i] = per[i];
	for (int i = 0;i < m;++i) {
		swap(cp[ L[i] ], cp[ R[i] ]);
		ma[ L[i] ] = R[i];
	}
	return true;
}
bool make_match() {
	vector<int> p(cp, cp+n+1);
	vector<int> pos(n+1);
	for (int i = 1;i <= n;++i)
		pos[ cp[i] ] = i;

	vector<bool> did(n+1);
	int m = n / 2;
	auto sw = [&](int a, int b) {
		swap(p[a], p[b]);
		swap(pos[p[a]], pos[p[b]]);
	};
	vector<int> O;
	auto putin = [&](int x) {
		O.pb(x);
	};
	auto popop = [&]() {
		while (O.size() >= 2) {
			int y = O.back(); O.pop_back();
			int x = O.back(); O.pop_back();
			int a = x, b = ma[y], c = y, d = ma[x];
			//cerr << "Before swap\n";
			::sw(a, b), ::sw(c, d);
			DE(a, b, c, d);
			res.pb(a, b);
		}
	};

	for (int i = 1;i <= m;++i) {
		if (did[i]) continue;
		did[i] = true;
		if (ma[i]) putin(i);
		while (i != p[i]) {
			int x = p[i];
			did[x] = true;
			if (ma[x]) putin(x);
			DE(i, x);
			sw(x, i);
		}
		popop();
	}
	//cerr << "ok\n";
	assert(O.empty());
	return true;
}
void solve() {
	cin >> n;
	for (int i = 1;i <= n;++i)
		cin >> per[i], pos[per[i]] = i;
	res.clear();
	res.reserve(n);
	if (!part() || !make_match()) {
		cout << -1 << '\n';
		return;
	}
	//cerr << "Per \n";
	int m = n / 2;
	for (int i = 1;i <= n;++i)
		pos[ per[i] ] = i;
	for (int i = 1;i <= m;++i) {
		vector<int> child;
		while (i != per[i]) {
			int x = per[i];
			res.pb(i, pos[i]);
			int a = i, b = pos[i], c = n-a+1, d = n-b+1;
			sw(a, b);
			sw(c, d);
		}
	}
	//cerr << "swap complete\n";
	for (int i = 1;i <= n;++i)
		if (i != per[i]) {
			cout << -1 << '\n';
			return ;
		}

	cout << res.size() << ' ' << res.size() << '\n';
	for (auto [a, b] : res)
		cout << a << ' ' << b << '\n';
 
}
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--)
		solve();
}

Compilation message (stderr)

cat.cpp: In lambda function:
cat.cpp:13:17: warning: statement has no effect [-Wunused-value]
   13 | #define DE(...) 0
      |                 ^
cat.cpp:78:4: note: in expansion of macro 'DE'
   78 |    DE(a, b, c, d);
      |    ^~
cat.cpp: In function 'bool make_match()':
cat.cpp:13:17: warning: statement has no effect [-Wunused-value]
   13 | #define DE(...) 0
      |                 ^
cat.cpp:91:4: note: in expansion of macro 'DE'
   91 |    DE(i, x);
      |    ^~
cat.cpp: In function 'void solve()':
cat.cpp:117:8: warning: unused variable 'x' [-Wunused-variable]
  117 |    int x = per[i];
      |        ^

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