Submission #412195

#	Time	Username	Problem	Language	Result	Execution time	Memory
412195		Theo830	Xor Sort (eJOI20_xorsort)	C++17	25 / 100	1075 ms	17560 KiB

xorsort

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e9+7;
ll MOD = 1e9+7;
typedef pair<ll,ll> ii;
#define iiii pair<ii,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define rf(i,a,b) for(long long i=a;i>=b;i--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define w(t) while(t--)
#define c(n); cin>>n;
#define p(n) cout<<n;
#define pl(n) cout<<n<<"\n";
#define ps(n); cout<<n<<" ";
#define F first
#define S second
#define pb(a) push_back(a)
#define all(x) (x).begin(), (x).end()
#define ull unsigned long long
#define vll vector<ll>
#define vii vector<ii>
#define mkp make_pair
#define ld long double
#define arrin(a,n) f(i,0,n){cin>>a[i];}
#define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
#define printclock cerr<<"Time : "<<*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define PI (2*acos(0))
#define EPS 1e-18
const long long N = 1e5+5;
const long long M = 1e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> distr;
ll rnd(ll a, ll b){return distr(rng)%(b-a+1)+a;}
void YESNO(ll a){if(!!a){pl("Yes");}else{pl("No");}}
void filesin(void){freopen("amusing.in","r",stdin);}
void filesout(void){freopen("amusing.out","w",stdout);}
///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
///Codeforces Round #679 (Div. 2, based on Technocup 2021 Elimination Round 1)
int main(void){
    fastio;
    ll n,s;
    cin>>n>>s;
    ll arr[n];
    arrin(arr,n);
    bool swaped = 1;
    vii vale;
    while(swaped){
        swaped = 0;
        f(i,0,n-1){
            if(arr[i] > arr[i+1]){
                vale.pb(ii(i+1,i));
                arr[i+1] ^= arr[i];
                arr[i] ^= arr[i+1];
                arr[i+1] ^= arr[i];
                vale.pb(ii(i,i+1));
                vale.pb(ii(i+1,i));
                swaped = 1;
            }
        }
    }
    assert(is_sorted(arr,arr+n));
    cout<<vale.size()<<endl;
    for(auto x:vale){
        cout<<x.F+1<<" "<<x.S+1<<endl;
    }
}

Compilation message (stderr)

xorsort.cpp: In function 'void filesin()':
xorsort.cpp:36:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 | void filesin(void){freopen("amusing.in","r",stdin);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
xorsort.cpp: In function 'void filesout()':
xorsort.cpp:37:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 | void filesout(void){freopen("amusing.out","w",stdout);}
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40