oj.uz

Submission #48279

# Submission time Handle Problem Language Result Execution time Memory
48279 2018-05-11T10:48:37 Z repeating Swap (BOI16_swap) C++11
0 / 100
 2 ms 564 KB 
#include <bits/stdc++.h>
//#include "rail.h"
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%Id",&x)
#define SF2(x,y) scanf("%Id%Id",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()

using namespace std;
const long long INF = 1e16;
const long long MOD = 1e15+9;
const int MX=200015;
int n;
int a[MX];
int par[MX];
int DSU(int x){
    if(par[x]==x)R x;
    else R par[x]=DSU(par[x]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        par[i]=i;
    }
    for(int i=1;i<=n/2;i++){
        int i1=i*2,i2=i*2+1;
        if(i2>n){
            if(a[i]>a[i1])par[i]=i1;
        }
        else{
            if(a[i1]<a[i2]&&a[i]>a[i1]){
                par[i]=i1;
            }
            if(a[i2]<a[i1]&&a[i]>a[i2]){
                par[i]=i2;
            }
        }
    }
    for(int i=1;i<=n/2;i++){
        int i1=i*2,i2=(i*2)+1;
//        cout<<i<<" "<<i1<<" "<<i2<<endl;
        if(i2>n){
            if(a[i]>a[i1])swap(a[i],a[i1]);
        }
        else{
            int p=DSU(i),p1=DSU(i1),p2=DSU(i2);
//            cout<<p<<" "<<p1<<" "<<p2<<endl;
            if(a[i1]<a[i2]&&a[i]>a[i1]){
                swap(a[i],a[i1]);
            }
            if(a[i2]<a[i1]&&a[i]>a[i2]){
                if(p1<p2){
                    if(a[i]<a[i1]){
                        swap(a[i],a[i2]);
                        swap(a[i1],a[i2]);
                    }
                    else{
                        swap(a[i],a[i2]);
                    }
                }
                else{
                    if(a[i]<a[i1]){
                        swap(a[i],a[i2]);
                    }
                    else{
                        swap(a[i],a[i2]);
                        swap(a[i1],a[i2]);
                    }
                }
            }
        }
//        cout<<i<<" "<<n/2<<endl;
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
}

Compilation message

swap.cpp: In function 'int main()':
swap.cpp:60:17: warning: unused variable 'p' [-Wunused-variable]
             int p=DSU(i),p1=DSU(i1),p2=DSU(i2);
                 ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 564 KB Output isn't correct
2 Halted 0 ms 0 KB -