oj.uz

Submission #475022

# Submission time Handle Problem Language Result Execution time Memory
475022 2021-09-20T13:35:09 Z hhhhaura Cat (info1cup19_cat) C++14
40 / 100
 590 ms 15904 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>
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 = 1; j < temp.size(); 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: In function 'void solver::solve()':
cat.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for(int j = 0; j < temp.size(); j += 2)
      |                   ~~^~~~~~~~~~~~~
cat.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    for(int j = 1; j < temp.size(); j ++)
      |                   ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Correct number of moves

Subtask #2
4.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 540 KB Correct number of moves
2 Correct 26 ms 512 KB Correct number of moves

Subtask #3
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Correct number of moves
2 Correct 26 ms 540 KB Correct number of moves
3 Correct 26 ms 512 KB Correct number of moves
4 Correct 30 ms 1100 KB Correct number of moves
5 Correct 11 ms 584 KB Correct number of moves
6 Correct 9 ms 460 KB Correct number of moves

Subtask #4
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 540 KB Correct number of moves
2 Correct 26 ms 512 KB Correct number of moves
3 Correct 553 ms 13772 KB Correct number of moves
4 Correct 517 ms 12620 KB Correct number of moves
5 Correct 573 ms 15812 KB Correct number of moves

Subtask #5
14.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Correct number of moves
2 Correct 26 ms 540 KB Correct number of moves
3 Correct 26 ms 512 KB Correct number of moves
4 Correct 30 ms 1100 KB Correct number of moves
5 Correct 11 ms 584 KB Correct number of moves
6 Correct 9 ms 460 KB Correct number of moves
7 Correct 553 ms 13772 KB Correct number of moves
8 Correct 517 ms 12620 KB Correct number of moves
9 Correct 573 ms 15812 KB Correct number of moves
10 Correct 561 ms 12096 KB Correct number of moves
11 Correct 498 ms 10400 KB Correct number of moves
12 Correct 549 ms 14196 KB Correct number of moves
13 Correct 590 ms 15904 KB Correct number of moves
14 Correct 524 ms 14044 KB Correct number of moves