# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
315190 |
2020-10-22T04:19:04 Z |
casperwang |
Cat (info1cup19_cat) |
C++14 |
|
594 ms |
21196 KB |
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int MAXN = 3000000;
int t, n;
int a[MAXN+1];
int c[MAXN+1];
int p[MAXN+1];
bool need[MAXN+1];
int tmp, cnt;
vector <pii> ans;
void solve(int N) {
for (int i = 1; i <= N; i++) {
if (a[i] != i) {
if (!need[i] && !need[p[i]]) {
ans.pb(pii(i, p[i]));
swap(a[n-i+1], a[n-p[i]+1]);
swap(p[a[n-i+1]], p[a[n-p[i]+1]]);
swap(a[i], a[p[i]]);
swap(p[a[i]], p[a[p[i]]]);
} else {
if (need[i] && need[p[i]])
need[i] = need[p[i]] = 0;
ans.pb(pii(i, n-p[i]+1));
swap(a[n-i+1], a[n-p[i]+1]);
swap(p[a[n-i+1]], p[a[n-p[i]+1]]);
swap(a[i], a[p[i]]);
swap(p[a[i]], p[a[p[i]]]);
}
}
}
cnt = 0;
for (int i = 1; i <= N; i++) {
if (need[i]) {
if (cnt % 2) {
ans.pb(pii(i, n-tmp+1));
ans.pb(pii(i, tmp));
}
cnt++;
tmp = i;
}
}
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> t;
while (t--) {
cin >> n;
bool tf = 1;
for (int i = 1; i <= n; i++)
cin >> a[i], p[a[i]] = i;
for (int i = 1; i <= n; i++)
need[i] = 0, c[i] = a[i];
ans.clear();
cnt = 0;
for (int i = 1; i <= n/2 && tf; i++) {
if (abs(a[n-i+1] + a[i]) != n+1) tf = 0;
if (a[i] > n/2) {
swap(a[n-i+1], a[i]);
p[a[n-i+1]] = n-i+1;
p[a[i]] = i;
need[i] = 1;
cnt++;
}
}
if (cnt % 2) tf = 0;
if (!tf) {
cout << -1 << "\n";
} else {
solve(n/2);
cout << ans.size() << " " << ans.size() << "\n";
for (pii o : ans) {
cout << o.ff << " " << o.ss << "\n";
swap(c[o.ff], c[o.ss]);
swap(c[n-o.ff+1], c[n-o.ss+1]);
}
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
5 ms |
384 KB |
Valid reconstruction |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
632 KB |
Output is correct |
2 |
Correct |
22 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
5 ms |
384 KB |
Valid reconstruction |
2 |
Correct |
22 ms |
632 KB |
Output is correct |
3 |
Correct |
22 ms |
640 KB |
Output is correct |
4 |
Partially correct |
30 ms |
744 KB |
Valid reconstruction |
5 |
Partially correct |
9 ms |
512 KB |
Valid reconstruction |
6 |
Partially correct |
9 ms |
512 KB |
Valid reconstruction |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
632 KB |
Output is correct |
2 |
Correct |
22 ms |
640 KB |
Output is correct |
3 |
Correct |
551 ms |
15596 KB |
Output is correct |
4 |
Correct |
484 ms |
14952 KB |
Output is correct |
5 |
Correct |
533 ms |
18724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
5 ms |
384 KB |
Valid reconstruction |
2 |
Correct |
22 ms |
632 KB |
Output is correct |
3 |
Correct |
22 ms |
640 KB |
Output is correct |
4 |
Partially correct |
30 ms |
744 KB |
Valid reconstruction |
5 |
Partially correct |
9 ms |
512 KB |
Valid reconstruction |
6 |
Partially correct |
9 ms |
512 KB |
Valid reconstruction |
7 |
Correct |
551 ms |
15596 KB |
Output is correct |
8 |
Correct |
484 ms |
14952 KB |
Output is correct |
9 |
Correct |
533 ms |
18724 KB |
Output is correct |
10 |
Partially correct |
534 ms |
14620 KB |
Valid reconstruction |
11 |
Partially correct |
482 ms |
12812 KB |
Valid reconstruction |
12 |
Partially correct |
547 ms |
18792 KB |
Valid reconstruction |
13 |
Partially correct |
594 ms |
21196 KB |
Valid reconstruction |
14 |
Partially correct |
539 ms |
18792 KB |
Valid reconstruction |