oj.uz

Submission #475023

# Submission time Handle Problem Language Result Execution time Memory
475023 2021-09-20T13:45:06 Z hhhhaura Cat (info1cup19_cat) C++14
100 / 100
 603 ms 15748 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
using namespace std;
#define pii pair<int, int>
#ifdef wiwihorz
#define print(a...) cerr << "Line: " << __LINE__, kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R)cerr << *L << " \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace solver {
	int n;
	vector<int> a, b, vis;
	vector<pii> ans;
	void init_(int _n) {
		n = _n;
		a.assign(n + 1, 0);
		b.assign(n + 1, 0);
		ans.clear();
	}
	void sswap(int x, int y) {
		ans.push_back({x, y});
		swap(a[x], a[y]);
		swap(a[n - x + 1], a[n - y + 1]);
	}
	int get(int x) {
		return x > n / 2 ? n - x + 1: x;
	}
	void solve() {
		int cnt = 0;
		rep(i, 1, n / 2) {
			if(a[i] + a[n - i + 1] != n + 1) {
				cout << "-1\n";
				return;
			}
			if(a[i] > n / 2) cnt ++;
		}
		if(cnt & 1) {
			cout << "-1\n";
			return;
		}
		vector<int> temp;
		vis.assign(n + 1, 0);
		int pre = 0;
		rep(i, 1, n / 2) if(!vis[i]) {
			temp.clear(), vis[i] = 1;
			if(a[i] > n / 2) temp.push_back(i);
			for(int j = get(a[i]); j != i; j = get(a[j])) {
				if(a[j] > n / 2) temp.push_back(j);
				vis[j] = 1;
			}
			if(temp.size() % 2 == 1) {
				if(pre) sswap(pre, n - temp.back() + 1), pre = 0;
				else pre = temp.back();
				temp.pop_back();
			}
			for(int j = 0; j < temp.size(); j += 2) 
				sswap(temp[j], n - temp[j + 1] + 1);
		}
		vis.assign(n + 1, 0);
		rep(i, 1, n / 2) if(!vis[i]) {
			temp.clear(), vis[i] = 1;
			temp.push_back(i);
			for(int j = get(a[i]); j != i; j = get(a[j])) {
				temp.push_back(j), vis[j] = 1;
			}
			for(int j = signed(temp.size()) - 1; j > 0; j --) 
				sswap(temp[j], temp[j -1]);
		}
		cout << ans.size() << " " << ans.size() << "\n";
		for(auto i : ans) cout << i.first << " " << i.second << "\n";
	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int t; cin >> t;
	while(t--) {
		int n; cin >> n;
		init_(n);
		rep(i, 1, n) cin >> a[i];
		solve();
	}
	return 0;
}

Compilation message

cat.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
cat.cpp:12:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 | void vprint(auto L, auto R) { while(L < R)cerr << *L << " \n"[next(L) == R], ++L; }
      |             ^~~~
cat.cpp:12:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 | void vprint(auto L, auto R) { while(L < R)cerr << *L << " \n"[next(L) == R], ++L; }
      |                     ^~~~
cat.cpp: In function 'void solver::solve()':
cat.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for(int j = 0; j < temp.size(); j += 2)
      |                   ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 528 KB Output is correct
2 Correct 25 ms 512 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 26 ms 528 KB Output is correct
3 Correct 25 ms 512 KB Output is correct
4 Correct 28 ms 580 KB Output is correct
5 Correct 10 ms 332 KB Output is correct
6 Correct 9 ms 332 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 528 KB Output is correct
2 Correct 25 ms 512 KB Output is correct
3 Correct 551 ms 13780 KB Output is correct
4 Correct 536 ms 12532 KB Output is correct
5 Correct 580 ms 15748 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 26 ms 528 KB Output is correct
3 Correct 25 ms 512 KB Output is correct
4 Correct 28 ms 580 KB Output is correct
5 Correct 10 ms 332 KB Output is correct
6 Correct 9 ms 332 KB Output is correct
7 Correct 551 ms 13780 KB Output is correct
8 Correct 536 ms 12532 KB Output is correct
9 Correct 580 ms 15748 KB Output is correct
10 Correct 549 ms 11348 KB Output is correct
11 Correct 513 ms 9692 KB Output is correct
12 Correct 582 ms 13596 KB Output is correct
13 Correct 603 ms 15264 KB Output is correct
14 Correct 551 ms 13316 KB Output is correct