oj.uz

Submission #146693

# Submission time Handle Problem Language Result Execution time Memory
146693 2019-08-25T08:53:37 Z evpipis Swap (BOI16_swap) C++
0 / 100
 8 ms 5116 KB 
#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

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.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 32.0

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