oj.uz

Submission #315164

# Submission time Handle Problem Language Result Execution time Memory
315164 2020-10-22T03:39:54 Z Kevin_Zhang_TW Cat (info1cup19_cat) C++17
36.25 / 100
 581 ms 15232 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;
	if (!part()) {
		cout << -1 << '\n';
		return;
	}
	res.clear();
	res.reserve(n);
	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 sw(int, int)':
cat.cpp:12:17: warning: statement has no effect [-Wunused-value]
   12 | #define DE(...) 0
      |                 ^
cat.cpp:21:2: note: in expansion of macro 'DE'
   21 |  DE(a, b, per[a], per[b]);
      |  ^~
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
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correctly distinguished between possibility and impossibility

Subtask #2
10.0 / 10.0

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

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correctly distinguished between possibility and impossibility
2 Correct 21 ms 632 KB Output is correct
3 Correct 21 ms 640 KB Output is correct
4 Correct 26 ms 640 KB Correctly distinguished between possibility and impossibility
5 Correct 10 ms 512 KB Correctly distinguished between possibility and impossibility
6 Correct 8 ms 512 KB Correctly distinguished between possibility and impossibility

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 632 KB Output is correct
2 Correct 21 ms 640 KB Output is correct
3 Correct 513 ms 13376 KB Output is correct
4 Correct 474 ms 12100 KB Output is correct
5 Correct 521 ms 14816 KB Output is correct

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correctly distinguished between possibility and impossibility
2 Correct 21 ms 632 KB Output is correct
3 Correct 21 ms 640 KB Output is correct
4 Correct 26 ms 640 KB Correctly distinguished between possibility and impossibility
5 Correct 10 ms 512 KB Correctly distinguished between possibility and impossibility
6 Correct 8 ms 512 KB Correctly distinguished between possibility and impossibility
7 Correct 513 ms 13376 KB Output is correct
8 Correct 474 ms 12100 KB Output is correct
9 Correct 521 ms 14816 KB Output is correct
10 Correct 524 ms 11648 KB Correctly distinguished between possibility and impossibility
11 Correct 467 ms 9840 KB Correctly distinguished between possibility and impossibility
12 Correct 501 ms 13524 KB Correctly distinguished between possibility and impossibility
13 Correct 581 ms 15232 KB Correctly distinguished between possibility and impossibility
14 Correct 493 ms 13068 KB Correctly distinguished between possibility and impossibility