oj.uz

Submission #474996

# Submission time Handle Problem Language Result Execution time Memory
474996 2021-09-20T12:14:27 Z hhhhaura Cat (info1cup19_cat) C++14
61 / 100
 668 ms 24300 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:82: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]
   82 |   for(int i = 0; i < temp.size(); i += 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 27 ms 512 KB Output is correct
2 Correct 25 ms 468 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 27 ms 512 KB Output is correct
3 Correct 25 ms 468 KB Output is correct
4 Partially correct 28 ms 588 KB Valid reconstruction
5 Partially correct 11 ms 448 KB Valid reconstruction
6 Partially correct 9 ms 352 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 512 KB Output is correct
2 Correct 25 ms 468 KB Output is correct
3 Correct 579 ms 18716 KB Output is correct
4 Correct 583 ms 18680 KB Output is correct
5 Correct 668 ms 24300 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 27 ms 512 KB Output is correct
3 Correct 25 ms 468 KB Output is correct
4 Partially correct 28 ms 588 KB Valid reconstruction
5 Partially correct 11 ms 448 KB Valid reconstruction
6 Partially correct 9 ms 352 KB Valid reconstruction
7 Correct 579 ms 18716 KB Output is correct
8 Correct 583 ms 18680 KB Output is correct
9 Correct 668 ms 24300 KB Output is correct
10 Partially correct 575 ms 13152 KB Valid reconstruction
11 Partially correct 597 ms 12088 KB Valid reconstruction
12 Partially correct 586 ms 20544 KB Valid reconstruction
13 Partially correct 625 ms 21904 KB Valid reconstruction
14 Partially correct 563 ms 20220 KB Valid reconstruction