Submission #734810

#TimeUsernameProblemLanguageResultExecution timeMemory
734810NeltXor Sort (eJOI20_xorsort)C++17
0 / 100
1 ms212 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> /* DEFINES */ #define S second #define F first #define ll long long #define ull unsigned long long #define ld long double #define npos ULLONG_MAX #define INF LLONG_MAX #define vv(a) vector<a> #define pp(a, b) pair<a, b> #define pq(a) priority_queue<a> #define qq(a) queue<a> #define ss(a) set<a> #define mm(a, b) map<a, b> #define ump(a, b) unordered_map<a, b> #define sync \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); #define elif else if #define endl "\n" #define allc(a) begin(a), end(a) #define all(a) a, a + sizeof(a) / sizeof(a[0]) #define pb push_back #define logi(a) __lg(a) #define sqrt(a) sqrtl(a) #define mpr make_pair #define ins insert using namespace std; using namespace __gnu_pbds; using namespace __cxx11; typedef char chr; typedef basic_string<chr> str; template <typename T, typename key = less<T>> using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll N = 1005; vv(pp(ll, ll)) ans; ll a[N]; void solve() { ll n; cin >> n; for (ll i = 1; i <= n; i++) cin >> a[i]; for (ll bit = 19; bit >= 0; bit--) { for (ll i = 1; i < n; i++) { if ((a[i] >> bit & 1) and !(a[i + 1] >> bit & 1)) ans.pb(mpr(i + 1, i)), a[i + 1] ^= a[i]; if ((a[i] ^ a[i + 1]) < a[i]) ans.pb(mpr(i, i + 1)), a[i] ^= a[i + 1]; } } assert(is_sorted(a + 1, a + n + 1)); cout << ans.size() << endl; for (auto [a, b] : ans) cout << a << ' ' << b << endl; } /* */ int main() { sync // precomp(); ll t = 1; // cin >> t; for (ll i = 1; i <= t; i++) // cout << "Case #" << i << ": ", solve(); cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...