Submission #563442

#	Time	Username	Problem	Language	Result	Execution time	Memory
563442		nghiass001	Swap (BOI16_swap)	C++17	100 / 100	97 ms	16484 KiB

swap

#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], used[N];
vector<int> *Q[N];

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

int query(int u) {
    if (u < 0) return a[-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) {
        if (Q[u]->at(i) > 0) del(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 if (vmin == vR) {
            Q[i*2]->push_back(i);
            Q[i*2 + 1] = Q[i*2];
        }
        else {
            exit(1);
        }

        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 (stderr)

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:27:5: note: in expansion of macro 'REP'
   27 |     REP(i, 0, Q[u]->size()) if (query(Q[u]->at(i)) == val) {
      |     ^~~
swap.cpp: In function 'int main()':
swap.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(file".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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