oj.uz

Submission #563423

# Submission time Handle Problem Language Result Execution time Memory
563423 2022-05-17T07:42:54 Z nghiass001 Swap (BOI16_swap) C++17
0 / 100
 0 ms 212 KB 
#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
const int N = 2e5 + 5, INF = 0x3c3c3c3c;
int n, res, a[N];
vector<int> *Q[N];

void Enter() {
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
}

int query(int u) {
    int val = INF;
    for(int v : *Q[u]) {
        if (v == u) val = min(val, a[u]);
        else val = min(val, query(v));
    }
    return val;
}

void del(int u, int val) {
    REP(i, 0, Q[u]->size()) if (query(Q[u]->at(i)) == val) {
        swap(Q[u]->at(i), Q[u]->back()); Q[u]->pop_back();
        return;
    }
}

void Process() {
    FOR(i, 1, n) {
        Q[i] = new vector<int>();
        Q[i]->push_back(i);
    }
    FOR(i, 1, n) {
        int vL = (i*2 <= n ? a[i*2] : INF);
        int vR = (i*2 + 1 <= n ? a[i*2 + 1] : INF);
        int vP = query(i);
        int vmin = min({vL, vR, vP});
        if (vmin == vP) {
            del(i, vP);
        }
        else if (vmin == vL) {
            Q[i*2] = Q[i];
        }
        else {
            Q[i*2]->push_back(i);
            Q[i*2 + 1] = Q[i*2];
        }

        cout << vmin << ' ';
    }
}

int main()
{
    #define file "t"
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    if (fopen(file".inp","r")) {
        freopen(file".inp","r",stdin);
        //freopen(file".out","w",stdout);
    }
    Enter();
    Process();
}

Compilation message

swap.cpp: In function 'void del(int, int)':
swap.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
swap.cpp:26:5: note: in expansion of macro 'REP'
   26 |     REP(i, 0, Q[u]->size()) if (query(Q[u]->at(i)) == val) {
      |     ^~~
swap.cpp: In function 'int main()':
swap.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(file".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -