Submission #146693

#	Time	Username	Problem	Language	Result	Execution time	Memory
146693		evpipis	Swap (BOI16_swap)	C++98	0 / 100	8 ms	5116 KiB

swap

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
const int len = 2e5+5;
int val[len];
vector<int> vec[len];

int fin(int i){
    if (!i) return len;

    if (vec[i].empty()) return fin(i/2);
    return min(vec[i].back(), fin(i/2));
}

void del(int i, int v){
    if (!i) return;

    if (!vec[i].empty() && vec[i].back() == v)
        vec[i].pop_back();
    else
        del(i/2, v);
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &val[i]);

    for (int i = 1; i <= n; i++){
        if (val[i] >= 1){
            int mn = i;
            if (2*i <= n && val[2*i] <= val[mn])
                mn = 2*i;
            if (2*i+1 <= n && val[2*i+1] <= val[mn])
                mn = 2*i+1;

            if (mn == 2*i)
                swap(val[i], val[2*i]);
            if (mn == 2*i+1){
                swap(val[i], val[2*i+1]);
                vec[i].pb(val[2*i]);
                vec[i].pb(val[2*i+1]);
                if (vec[i][0] < vec[i][1])
                    swap(vec[i][0], vec[i][1]);
                val[2*i] = 0;
                val[2*i+1] = 0;
            }
        }
        else{
            val[i] = fin(i);
            int mn = i;
            if (2*i <= n && val[2*i] <= val[mn])
                mn = 2*i;
            if (2*i+1 <= n && val[2*i+1] <= val[mn])
                mn = 2*i+1;

            if (mn == i)
                del(i, val[i]);
            if (mn == 2*i){
                val[i] = 0;
                swap(val[i], val[2*i]);
            }
            if (mn == 2*i+1){
                swap(val[i], val[2*i+1]);
                vec[i].pb(val[2*i]);
                val[2*i] = val[2*i+1] = 0;
            }
        }
    }

    for (int i = 1; i <= n; i++)
        printf("%d ", val[i]);
    printf("\n");
    return 0;
}

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
swap.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &val[i]);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32