oj.uz

Submission #315276

# Submission time Handle Problem Language Result Execution time Memory
315276 2020-10-22T08:09:17 Z Kevin_Zhang_TW Cat (info1cup19_cat) C++17
51.25 / 100
 589 ms 18168 KB 
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 3000010;
int per[MAX_N], n, pos[MAX_N];
void fail() {
	puts("-1"), exit(0);
}
void sw(int a, int b) {
	//DE(a, b, per[a], per[b]);
	swap(per[a], per[b]);
	swap(pos[per[a]], pos[per[b]]);
}
int rev(int i) {
	return n - i + 1;
}
vector< pair<int,int> > res;
bool part() {
	vector<int> L, R;
	int m = n / 2;
	for (int i = 1;i <= m;++i)
		if (per[i] > m)
			L.pb(i);
	for (int i = m+1;i <= n;++i)
		if (per[i] <= m)
			R.pb(i);
 
	assert(L.size() == R.size());
 
	reverse(AI(R));
	m = L.size();
	if (m&1) return false;
	for (int i = 0;i < m;++i)
		if (L[i] != rev(R[i])) 
			return false;
	for (int i = 0;i < m;i += 2) {
		res.pb( L[i], R[i+1] );
		int a = L[i], b = R[i+1], c = rev(L[i]), d = rev(b);
		sw(a, b);
		sw(c, d);
	}
	return true;
}
void solve() {
	cin >> n;
	for (int i = 1;i <= n;++i)
		cin >> per[i], pos[per[i]] = i;
	res.clear();
	res.reserve(n);
	if (!part()) {
		cout << -1 << '\n';
		return;
	}
	int m = n / 2;
 
	DE(m);
	for (int i = 1;i <= m;++i) {
		while (i != per[i]) {
			int x = per[i];
			res.pb(i, pos[i]);
			int a = i, b = pos[i], c = n-a+1, d = n-b+1;
 
			sw(a, b);
			sw(c, d);
		}
	}
	debug(per+1, per+1+n);
	for (int i = 1;i <= n;++i)
		if (i != per[i]) {
			cout << -1 << '\n';
			return;
		}
 
	cout << res.size() << ' ' << res.size() << '\n';
	for (auto [a, b] : res)
		cout << a << ' ' << b << '\n';
 
}
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--)
		solve();
}

Compilation message

cat.cpp: In function 'void solve()':
cat.cpp:12:17: warning: statement has no effect [-Wunused-value]
   12 | #define DE(...) 0
      |                 ^
cat.cpp:67:2: note: in expansion of macro 'DE'
   67 |  DE(m);
      |  ^~
cat.cpp:70:8: warning: unused variable 'x' [-Wunused-variable]
   70 |    int x = per[i];
      |        ^
cat.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
cat.cpp:78:2: note: in expansion of macro 'debug'
   78 |  debug(per+1, per+1+n);
      |  ^~~~~

Subtask #1
5.25 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 384 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 640 KB Output is correct
2 Correct 22 ms 632 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 384 KB Valid reconstruction
2 Correct 22 ms 640 KB Output is correct
3 Correct 22 ms 632 KB Output is correct
4 Partially correct 28 ms 768 KB Valid reconstruction
5 Partially correct 11 ms 512 KB Valid reconstruction
6 Partially correct 9 ms 512 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 640 KB Output is correct
2 Correct 22 ms 632 KB Output is correct
3 Correct 504 ms 13372 KB Output is correct
4 Correct 475 ms 12224 KB Output is correct
5 Correct 510 ms 14960 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 384 KB Valid reconstruction
2 Correct 22 ms 640 KB Output is correct
3 Correct 22 ms 632 KB Output is correct
4 Partially correct 28 ms 768 KB Valid reconstruction
5 Partially correct 11 ms 512 KB Valid reconstruction
6 Partially correct 9 ms 512 KB Valid reconstruction
7 Correct 504 ms 13372 KB Output is correct
8 Correct 475 ms 12224 KB Output is correct
9 Correct 510 ms 14960 KB Output is correct
10 Partially correct 567 ms 14500 KB Valid reconstruction
11 Partially correct 509 ms 11984 KB Valid reconstruction
12 Partially correct 534 ms 15328 KB Valid reconstruction
13 Partially correct 589 ms 18168 KB Valid reconstruction
14 Partially correct 533 ms 15576 KB Valid reconstruction