oj.uz

Submission #474990

# Submission time Handle Problem Language Result Execution time Memory
474990 2021-09-20T12:08:54 Z hhhhaura Cat (info1cup19_cat) C++14
61 / 100
 636 ms 37388 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()
#define ceil(a, b) ((a + b - 1) / (b))

using namespace std;

#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#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, top, inv;
	vector<pii> ans;
	void init_(int _n) {
		n = _n;
		a.assign(n + 1, 0);
		b.assign(n + 1, 0);
		vis.assign(n + 1, -1);
		top.assign(n + 1, 0);
		inv.assign(n + 1, 0);
		ans.clear();
	}
	void dfs(int x) {
		vis[x] = 0;
		if(!b[x]) {
			if(vis[a[x]] == -1)
				dfs(a[x]), top[x] = top[a[x]];
			top[a[x]] = 0;
		}
		else top[x] = 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) {
				b[i] = 1, cnt++;
				swap(a[i], a[n - i + 1]);
			}
		}
		if(cnt & 1) {
			cout << "-1\n";
			return;
		}
		rep(i, 1, n / 2) {
			inv[a[i]] = i;
			if(vis[i] == -1) dfs(i);
		}
		rep(i, 1, n / 2) if(top[i] && b[top[i]]) {
//			print(i, top[i]);
			if(a[top[i]] != i && b[inv[i]]) {
				b[top[i]] = 0, b[inv[i]] = 0;
				ans.push_back({top[i], n - inv[i] + 1});
				swap(a[top[i]], a[inv[i]]);
				swap(a[n - top[i] + 1], a[n - inv[i] + 1]);
			}
		}
		vector<int> temp;
		rep(i, 1, n / 2) if(b[i]) temp.push_back(i);
//		print(temp.size());
//		vprint(all(temp));
//		assert(temp.size() % 2 == 0);
		for(int i = 0; i < temp.size(); i += 2) {
			int x = temp[i], y = temp[i + 1];
			ans.push_back({x, n - y + 1});
			swap(a[x], a[y]);
			swap(a[n - x + 1], a[n - y + 1]);
		}
		rep(i, 1, n / 2) if(a[i] != i && !vis[i]){
			int cur = a[i];
			temp.clear(), temp.push_back(i);
			vis[i] = 1;
			while(cur != i) {
				temp.push_back(cur);
				vis[cur] = 1;
				cur = a[cur];
			}
			rrep(j, 0, signed(temp.size()) - 2) {
				ans.push_back({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:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L, auto R) { while(L < R)cerr << *L << " \n"[next(L) == R], ++L; }
      |             ^~~~
cat.cpp:20:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | 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:83:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for(int i = 0; i < temp.size(); i += 2) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Output is correct
2 Correct 26 ms 700 KB Output is correct
3 Correct 25 ms 728 KB Output is correct
4 Partially correct 30 ms 1092 KB Valid reconstruction
5 Partially correct 14 ms 604 KB Valid reconstruction
6 Partially correct 9 ms 588 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 700 KB Output is correct
2 Correct 25 ms 728 KB Output is correct
3 Correct 564 ms 19384 KB Output is correct
4 Correct 558 ms 19360 KB Output is correct
5 Correct 636 ms 24876 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Output is correct
2 Correct 26 ms 700 KB Output is correct
3 Correct 25 ms 728 KB Output is correct
4 Partially correct 30 ms 1092 KB Valid reconstruction
5 Partially correct 14 ms 604 KB Valid reconstruction
6 Partially correct 9 ms 588 KB Valid reconstruction
7 Correct 564 ms 19384 KB Output is correct
8 Correct 558 ms 19360 KB Output is correct
9 Correct 636 ms 24876 KB Output is correct
10 Partially correct 597 ms 27024 KB Valid reconstruction
11 Partially correct 534 ms 26168 KB Valid reconstruction
12 Partially correct 588 ms 36324 KB Valid reconstruction
13 Partially correct 626 ms 37388 KB Valid reconstruction
14 Partially correct 576 ms 35960 KB Valid reconstruction