Submission #466027

#TimeUsernameProblemLanguageResultExecution timeMemory
466027SamAndXor Sort (eJOI20_xorsort)C++17
100 / 100
11 ms1004 KiB
#include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const int N = 1003, m = 20; int n, ty; int a[N]; vector<pair<int, int> > ans; void ubd(int x, int y) { ans.push_back(m_p(x, y)); a[x] ^= a[y]; } void solv2() { int nn = n; for (int j = m - 1; j >= 0; --j) { for (int i = 1; i < nn; ++i) { if ((a[i] & (1 << j))) { if ((a[i + 1] & (1 << j))) ubd(i, i + 1); else { ubd(i + 1, i); ubd(i, i + 1); } } } if ((a[nn] & (1 << j))) --nn; } for (int i = 1; i < n; ++i) assert(a[i] <= a[i + 1]); } void solv1() { vector<int> v; for (int i = 1; i <= n; ++i) v.push_back(a[i]); sort(all(v)); reverse(all(v)); for (int i = 0; i < sz(v); ++i) { int u = -1; for (int j = 1; j <= n - i; ++j) { if (i) { if (a[j] == (v[i] ^ v[i - 1])) u = j; } else { if (a[j] == v[i]) u = j; } } for (int j = 1; j < n - i; ++j) { ubd(j, j + 1); } for (int j = u + 1; j <= n - i; ++j) { ubd(j, j - 1); } for (int j = u - 2; j >= 1; --j) { ubd(j, j + 1); } } for (int i = n - 1; i >= 1; --i) ubd(i, i + 1); for (int i = 1; i < n; ++i) assert(a[i] < a[i + 1]); } void solv() { cin >> n >> ty; for (int i = 1; i <= n; ++i) cin >> a[i]; if (ty == 2) { solv2(); } else { solv1(); } cout << sz(ans) << "\n"; for (int i = 0; i < sz(ans); ++i) cout << ans[i].fi << ' ' << ans[i].se << "\n"; } int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif // SOMETHING ios_base::sync_with_stdio(false), cin.tie(0); int tt = 1; //cin >> tt; while (tt--) { solv(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...