oj.uz

Submission #412195

# Submission time Handle Problem Language Result Execution time Memory
412195 2021-05-26T15:34:03 Z Theo830 Xor Sort (eJOI20_xorsort) C++17
25 / 100
 1000 ms 17560 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 27 ms 764 KB Output is correct
5 Correct 32 ms 976 KB Output is correct
6 Correct 29 ms 976 KB Output is correct
7 Correct 29 ms 976 KB Output is correct
8 Correct 29 ms 976 KB Output is correct
9 Correct 31 ms 924 KB Output is correct
10 Correct 31 ms 976 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 56 ms 1464 KB Output is correct
13 Correct 56 ms 1484 KB Output is correct
14 Correct 56 ms 1484 KB Output is correct
15 Correct 59 ms 1484 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 27 ms 764 KB Output is correct
5 Correct 32 ms 976 KB Output is correct
6 Correct 29 ms 976 KB Output is correct
7 Correct 29 ms 976 KB Output is correct
8 Correct 29 ms 976 KB Output is correct
9 Correct 31 ms 924 KB Output is correct
10 Correct 31 ms 976 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 56 ms 1464 KB Output is correct
13 Correct 56 ms 1484 KB Output is correct
14 Correct 56 ms 1484 KB Output is correct
15 Correct 59 ms 1484 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 30 ms 848 KB Output is correct
18 Correct 50 ms 1084 KB Output is correct
19 Correct 51 ms 1112 KB Output is correct
20 Correct 53 ms 1068 KB Output is correct
21 Correct 52 ms 1120 KB Output is correct
22 Correct 52 ms 1120 KB Output is correct
23 Correct 52 ms 1060 KB Output is correct
24 Correct 49 ms 1000 KB Output is correct
25 Correct 51 ms 1004 KB Output is correct
26 Incorrect 100 ms 1688 KB Integer 59568 violates the range [0, 40000]
27 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 50 ms 1224 KB Output is correct
5 Execution timed out 1075 ms 17560 KB Time limit exceeded
6 Halted 0 ms 0 KB -