Submission #315341

#	Time	Username	Problem	Language	Result	Execution time	Memory
315341		Kevin_Zhang_TW	Cat (info1cup19_cat)	C++17	100 / 100	670 ms	13580 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 kout() {cerr << endl;}
template<class T1, class ...T2>
void kout (T1 v, T2 ...e) { cerr << v << ' ', kout(e...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;
int n;
vector<pair<int,int>> op;
// just the front half
void swap_sort(vector<int> p) {
	vector<int> pos(n+1);
	int m = n/2;
	for (int i = 0; i < n;++i)
		pos[ p[i] ] = i;
	auto sw = [&](int x, int y) {
		op.pb(x, y);
		swap(p[x], p[y]), swap(pos[p[x]], pos[p[y]]);
	};
	for (int i = 0;i < m;++i) {
		while (i+1 != p[i]) 
			sw(i, pos[i+1]);
	}
}
bool valid(vector<int> p) {
	int cnt = 0, m = n / 2;
	for (int l = 0, r = n-1;l < r;++l, --r) {
		if ((p[l]>m) ^ (p[r]<=m))
			return false;
		if (p[l] > m)
			++cnt;
	}
	if (cnt & 1) 
		return false;
	DE(cnt);
	vector<int> ln, rn;
	for (int i = 0;i < m;++i)
		if (p[i] > m)
			ln.pb(i);
	for (int i = n-1;i >= m;--i)
		if (p[i] <= m)
			rn.pb(i);

	assert(cnt == ln.size() && cnt == rn.size());
	vector<int> pos(n+1);
	for (int i = 0;i < n;++i)
		pos[ p[i] ] = i;
	auto sw = [&](int x, int y) {
		swap(p[x], p[y]), swap(pos[ p[x] ], pos[ p[y] ]);
	};
	auto do_op = [&](int x, int y) {
		int a = x, b = y, c = n - x - 1, d = n - y - 1;
		sw(a, b), sw(c, d);
	};
	for (int i = 0;i < cnt;i += 2)
		do_op(ln[i], rn[i+1]);

	for (int i = 0;i < m;++i) {
		while (i+1 != p[i]) {
			do_op(i, pos[i+1]);
		}
	}
	for (int i = 0;i < n;++i)
		if (p[i] != i+1)
			return false;
	return true;
}
// make p good enough so that I can do swap sort on it
vector<int> pair_good(vector<int> p) {
	vector<int> notp;
	vector<int> pos(n+1);
	vector<int> goodp(p);
	debug(AI(p));
	auto put = [&](int id) {
		DE(id);
		notp.pb(id);
	};
	auto sw = [&](int a, int b) {
		swap(p[a], p[b]), swap(pos[ p[a] ], pos[ p[b] ]);
	};
	auto do_op = [&](int x, int y) {
		DE(x, y);
		int a = x, b = y, c = n - a - 1, d = n - b - 1;
		swap( goodp[a], goodp[b] );
		swap( goodp[c], goodp[d] );
		op.pb(a, b);
	};
		
	auto pop = [&]() {
		while (notp.size() > 1) {
			int a = notp.back(); notp.pop_back();
			int b = notp.back(); notp.pop_back();
			do_op(a, n-b-1);
		}
	};
	int m = n / 2;
	vector<bool> ch(n), vis(n);
	int cnt = 0;
	for (int i = 0;i < m;++i)
		if (p[i] > m)
			swap(p[i], p[n-i-1]), ch[i] = true, ++cnt;


	for (int i = 0;i < m;++i) 
		pos[p[i]] = i;

	DE(cnt);
	debug(AI(p));
	for (int i = 0;i < m;++i) {
		if (vis[i]) continue;
		vis[i] = true;
		if (ch[i])
			put(i);
			
		while (i+1 != p[i]) {
			int x = p[i]-1;
			if (ch[x])
				put(x);

			vis[x] = true;
			sw(i, x);
		}
		pop();
	}
	assert(notp.empty());
	cerr << "GoodP\n";
	debug(AI(goodp));
	return goodp;
}
bool solve() {
	cin >> n;
	vector<int> p(n);
	for (int &i : p)
		cin >> i;
	debug(AI(p));
	if (!valid(p))
		return false;
	p = pair_good(p);
	swap_sort(p);
	return true;
}
signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		op.clear();
		if (!solve()) {
			cout << -1 << '\n';
		}
		else {
			cout << op.size() << ' ' << op.size() << '\n';
			for (auto [a, b] : op)
				cout << a+1 << ' ' << b+1 << '\n';
		}
	}
}

Compilation message (stderr)

cat.cpp: In function 'bool valid(std::vector<int>)':
cat.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
cat.cpp:46:2: note: in expansion of macro 'DE'
   46 |  DE(cnt);
      |  ^~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from cat.cpp:1:
cat.cpp:55:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  assert(cnt == ln.size() && cnt == rn.size());
      |         ~~~~^~~~~~~~~~~~
cat.cpp:55:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  assert(cnt == ln.size() && cnt == rn.size());
      |                             ~~~~^~~~~~~~~~~~
cat.cpp: In function 'std::vector<int> pair_good(std::vector<int>)':
cat.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 0
      |                    ^
cat.cpp:84:2: note: in expansion of macro 'debug'
   84 |  debug(AI(p));
      |  ^~~~~
cat.cpp: In lambda function:
cat.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
cat.cpp:86:3: note: in expansion of macro 'DE'
   86 |   DE(id);
      |   ^~
cat.cpp: In lambda function:
cat.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
cat.cpp:93:3: note: in expansion of macro 'DE'
   93 |   DE(x, y);
      |   ^~
cat.cpp: In function 'std::vector<int> pair_good(std::vector<int>)':
cat.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
cat.cpp:118:2: note: in expansion of macro 'DE'
  118 |  DE(cnt);
      |  ^~
cat.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 0
      |                    ^
cat.cpp:119:2: note: in expansion of macro 'debug'
  119 |  debug(AI(p));
      |  ^~~~~
cat.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 0
      |                    ^
cat.cpp:138:2: note: in expansion of macro 'debug'
  138 |  debug(AI(goodp));
      |  ^~~~~
cat.cpp: In function 'bool solve()':
cat.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 0
      |                    ^
cat.cpp:146:2: note: in expansion of macro 'debug'
  146 |  debug(AI(p));
      |  ^~~~~

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