Submission #146700

#	Time	Username	Problem	Language	Result	Execution time	Memory
146700		evpipis	Swap (BOI16_swap)	C++98	100 / 100	80 ms	12284 KiB

swap

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

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

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

    int ans = len;
    if (!vec[i].empty())
        ans = vec[i].back();

    if (!block[i])
        ans = min(ans, fin(i/2));
    return ans;
}

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

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

int out[len];

void upd(int n){
    int pos = 1;
    while (pos <= n && out[pos] == val[pos])
        pos++;

    if (pos <= n && val[pos] < out[pos])
        for (int i = 1; i <= n; i++)
            out[i] = val[i];
}

void solve(int n){
    for (int i = 1; i <= n; i++)
        out[i] = n;
    for (int bit = 0; bit < (1<<(n-1)); bit++){
        for (int j = 2; j <= n; j++)
            if (bit&(1<<(j-2)))
                swap(val[j/2], val[j]);

        upd(n);

        for (int j = n; j >= 2; j--)
            if (bit&(1<<(j-2)))
                swap(val[j/2], val[j]);
    }

    #ifndef TEST
    printf("brute: ");
    for (int i = 1; i <= n; i++)
        printf("%d ", out[i]);
    printf("\n");
    #endif
}

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

    #ifdef TEST
    int rem = 1000;
    while (rem--){
    printf("rem = %d\n", rem);
    int n = rand()%25+1;
    for (int i = 1; i <= n; i++)
        val[i] = i, block[i] = 0;
    random_shuffle(val+1, val+1+n);

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

    //solve(n);

    for (int i = 1; i <= n; i++){
        //printf("i = %d, tp = %d\n", i, val[i]);
        if (val[i] >= 1){
            block[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;

            //printf("mn = %d with %d\n", mn, val[mn]);

            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;

            //printf("mn = %d with %d\n", mn, val[mn]);

            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;
            }
        }

        //printf("val = %d, vec =", val[i]);
        //for (int j = 0; j < vec[i].size(); j++)
          //  printf(" %d", vec[i][j]);
        //printf("\n\n");
    }

    #ifdef TEST
    int same = 1;
    for (int i = 1; i <= n; i++)
        if (val[i] != out[i])
            same = 0;

    if (!same){
        printf("bru: ");
        for (int i = 1; i <= n; i++)
            printf("%d ", out[i]);
        printf("\n");

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

    printf("its correct\n");
    #endif

    #ifndef TEST
    //printf("optim: ");
    for (int i = 1; i <= n; i++)
        printf("%d ", val[i]);
    printf("\n");
    #endif
    return 0;
}
/*
9
7 8 6 2 3 9 5 1 4

6
5 4 1 6 2 3

5
4 1 5 3 2

19
11 15 2 3 4 7 6 18 10 17 16 12 14 8 9 19 1 5 13

18
4 15 2 17 10 12 8 11 18 6 9 16 7 14 3 13 1 5

24
22 20 3 7 14 13 19 2 15 1 6 12 17 21 10 5 16 23 9 4 11 24 18 8
*/

Compilation message (stderr)

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

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