oj.uz

Submission #315169

# Submission time Handle Problem Language Result Execution time Memory
315169 2020-10-22T03:42:49 Z Kevin_Zhang_TW Cat (info1cup19_cat) C++17
51.25 / 100
 585 ms 18036 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();
	for (int i = 0;i < m;++i)
		if (L[i] != rev(R[i])) 
			return false;
	if (L.size()&1) {
		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:69:2: note: in expansion of macro 'DE'
   69 |  DE(m);
      |  ^~
cat.cpp:72:8: warning: unused variable 'x' [-Wunused-variable]
   72 |    int x = per[i];
      |        ^
cat.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
cat.cpp:80:2: note: in expansion of macro 'debug'
   80 |  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 21 ms 640 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 21 ms 640 KB Output is correct
4 Partially correct 28 ms 760 KB Valid reconstruction
5 Partially correct 12 ms 512 KB Valid reconstruction
6 Partially correct 10 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 21 ms 640 KB Output is correct
3 Correct 506 ms 13380 KB Output is correct
4 Correct 498 ms 12076 KB Output is correct
5 Correct 533 ms 14956 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 21 ms 640 KB Output is correct
4 Partially correct 28 ms 760 KB Valid reconstruction
5 Partially correct 12 ms 512 KB Valid reconstruction
6 Partially correct 10 ms 512 KB Valid reconstruction
7 Correct 506 ms 13380 KB Output is correct
8 Correct 498 ms 12076 KB Output is correct
9 Correct 533 ms 14956 KB Output is correct
10 Partially correct 564 ms 14360 KB Valid reconstruction
11 Partially correct 513 ms 12112 KB Valid reconstruction
12 Partially correct 538 ms 15448 KB Valid reconstruction
13 Partially correct 585 ms 18036 KB Valid reconstruction
14 Partially correct 544 ms 15708 KB Valid reconstruction