Submission #634024

#TimeUsernameProblemLanguageResultExecution timeMemory
634024boris_mihovCat (info1cup19_cat)C++17
33.75 / 100
413 ms28156 KiB
#include <algorithm> #include <iostream> #include <numeric> #include <vector> typedef long long llong; const int MAXN = 100000 + 10; const int INF = 1e9; int n, m; int a[MAXN]; int posOf[MAXN]; std::vector < std::pair <int,int> > ops; inline void operation(int x, int y) { std::swap(a[x], a[y]); std::swap(a[n-x+1], a[n-y+1]); posOf[a[x]] = x; posOf[a[y]] = y; posOf[a[n-x+1]] = n-x+1; posOf[a[n-y+1]] = n-y+1; ops.emplace_back(x, y); } void solve() { int cnt = 0; ops.clear(); for (int i = 1 ; i <= n ; ++i) { if (a[n - i + 1] != n - a[i] + 1) { std::cout << -1 << '\n'; return; } posOf[a[i]] = i; if (i <= n/2) { cnt += (a[i] > n/2); } } if (cnt & 1) { std::cout << -1 << '\n'; return; } for (int i = 1 ; i <= n/2 ; ++i) { if (a[i] <= n/2) continue; int wantedSwap = n-a[i]+1; if (i != wantedSwap && a[wantedSwap] > n/2) { operation(i, n - wantedSwap + 1); } } int lastBig = 0; for (int i = 1 ; i <= n/2 ; ++i) { if (a[i] <= n/2) continue; if (lastBig != 0) { operation(i, n - lastBig + 1); lastBig = 0; } else { lastBig = i; } } for (int i = 1 ; i <= n ; ++i) { if (posOf[i] != i) { operation(i, posOf[i]); } } for (int i = 1 ; i <= n ; ++i) { if (a[i] != i) { std::cout << -1 << '\n'; return; } } std::cout << ops.size() << ' ' << ops.size() << '\n'; for (auto [x, y] : ops) { std::cout << x << ' ' << y << '\n'; } } void read() { std::cin >> n; for (int i = 1 ; i <= n ; ++i) { std::cin >> a[i]; } } void fastIO() { std::ios_base :: sync_with_stdio(0); std::cout.tie(nullptr); std::cin.tie(nullptr); } int tests; int main() { fastIO(); std::cin >> tests; while (tests--) { read(); solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...