Submission #442570

#TimeUsernameProblemLanguageResultExecution timeMemory
442570Theo830Xor Sort (eJOI20_xorsort)C++17
60 / 100
10 ms1484 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e9+7; const ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<ii,ll> #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); ll n,s; cin>>n>>s; ll arr[n]; f(i,0,n){ cin>>arr[i]; } vector<ii>ans; if(s == 1){ ll pre = 0; f(j,0,n){ ll maxi = -1; ll pos = 0; f(i,0,n-j){ maxi = max(maxi,arr[i] ^ pre); if(maxi == (arr[i] ^ pre)){ pos = i; } } pre = maxi; f(i,0,n-j-1){ ans.pb(ii(i+1,i+2)); arr[i] ^= arr[i+1]; } f(i,pos,n-j-1){ ans.pb(ii(i+2,i+1)); arr[i+1] ^= arr[i]; } for(ll i = pos-1;i >= 1;i--){ ans.pb(ii(i,i+1)); arr[i-1] ^= arr[i]; } } for(ll i = n-2;i >= 0;i--){ ans.pb(ii(i+1,i+2)); arr[i] ^= arr[i+1]; } assert(is_sorted(arr,arr+n)); } cout<<ans.size()<<"\n"; for(auto x:ans){ cout<<x.F<<" "<<x.S<<"\n"; } } /* 5 1 3 2 8 4 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...