oj.uz

Submission #1100671

# Submission time Handle Problem Language Result Execution time Memory
1100671 2024-10-14T12:35:38 Z vjudge1 Swap (BOI16_swap) C++17
0 / 100
 6 ms 29316 KB 
// Bolatulu
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define fx cout << fixed << setprecision(6);
#define md (tl+tr)/2
#define TL v+v, tl,md
#define TR v+v+1, md+1,tr
#define Tl t[v].l, tl,md
#define Tr t[v].r, md+1,tr
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define all(x) (x).begin(), (x).end()
#define int ull
#define cnk(n,k) mod(mod(f[(n)]*binpow(f[(n)-(k)],M-2))*binpow(f[(k)],M-2))
#define cnkf(n,k) mod(mod(f[(n)]*inv[(n)-(k)])*inv[(k)])

using namespace std;

typedef complex<double> cd;

struct mine{int l;int r;int i;};
struct edge{int u;int v;int w;};
struct tree{int l;int r;int val;};

bool cmp(edge a,edge b) {
    return a.w>b.w;
}

mt19937 RR((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
 
int random(int l, int r){
  return uniform_int_distribution<int>(l, r)(RR);
}

int M=998244353;

int mod1(int a,int b=M) {
    if (a<0)
        a=b+a%b;
    return a % b;
}

int binpow(int a,int n,int m=M) {
    a=mod1(a,m);
    if (!n)
        return 1;
    if (n&1)
        return (a * binpow(a,n-1))%m;
    int x = binpow(a,n>>1);
    return (x*x)%m; 
}

const double pi = acos(-1);
const cd I = sqrt(cd(-1));
const int INF=1e18+7;
const int N=1e6+7;
const int root = 5;
const int root_1 = 4404020;
const int root_pw = 1 << 20;
int mod=7340033;

int n,a[N],mp[N];
vector <int> d[N];

void solve() {
    cin >> n;
    for (int i=1;i<=n;i++)
        cin >> a[i];
    if (n==1) {
        cout << a[1];
        return;
    }
    if (n==2) {
        if (a[2]<a[1])
            swap(a[2],a[1]);
        cout << a[1] << ' ' << a[2];
        return;
    }
    for (int i=n+1;i<=4*n;i++)
        a[i]=INF;
    for (int i=1;i<=n;i++) {
        d[i].pb(a[i]);
        sort(all(d[i]));
        bool okk=false;
        for (auto now : d[i]) {
            if (mp[now])
                continue;
            a[i]=now;
            if (i*2>n)
                break;
            if (a[i]>a[i*2] or a[i]>a[i*2+1])
                okk=true;
            break;
        }
        if (okk) {
            for (auto now : d[i]) {
                if (mp[now])
                    continue;
                a[i]=now;
                if (i*2>n)
                    continue;
                d[i*2].pb(a[i]);
                if (a[i*2]<a[i*2+1]) {
                    a[i]=a[i*2];
                } else {
                    d[i*2+1].pb(a[i]);
                    d[i*2+1].pb(a[i*2]);
                    a[i]=a[i*2+1];
                }
            }
        }
        mp[a[i]]=true;
    }
    for (int i=1;i<=n;i++)
        cout << a[i] << ' ';
}   

signed main() {
    /*
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    */
    // fx
    kanagattandirilmagandiktarinizdan
    int test = 1, count = 1;
    // cin >> test;
    while (test--) {
        // cout << "Case " << count << ":\n";
        solve();
        if (test) {
            cout << '\n';
            count++;
        }
    }
    return 0;
}

// ctrl + shift + p make stress isis__Good isis__Generator

// g++ -std=c++17 (path) -o run
// .\run

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 6 ms 29264 KB Output is correct
3 Incorrect 5 ms 29316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 6 ms 29264 KB Output is correct
3 Incorrect 5 ms 29316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 6 ms 29264 KB Output is correct
3 Incorrect 5 ms 29316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 6 ms 29264 KB Output is correct
3 Incorrect 5 ms 29316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 6 ms 29264 KB Output is correct
3 Incorrect 5 ms 29316 KB Output isn't correct
4 Halted 0 ms 0 KB -