Submission #48279

#	Time	Username	Problem	Language	Result	Execution time	Memory
48279		repeating	Swap (BOI16_swap)	C++11	0 / 100	2 ms	564 KiB

swap

#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 (stderr)

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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32