Submission #465990

#TimeUsernameProblemLanguageResultExecution timeMemory
465990SamAndXor Sort (eJOI20_xorsort)C++17
40 / 100
10 ms1000 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]); cout << sz(ans) << "\n"; for (int i = 0; i < sz(ans); ++i) cout << ans[i].fi << ' ' << ans[i].se << "\n"; } void solv() { cin >> n >> ty; for (int i = 1; i <= n; ++i) cin >> a[i]; if (ty == 2) { solv2(); return; } } 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...