Submission #96946

#	Time	Username	Problem	Language	Result	Execution time	Memory
96946		Kastanda	Swap (BOI16_swap)	C++11	68 / 100	1163 ms	160308 KiB

swap

// Borrowed.
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
int n, l, r, A[N], R[N], rev[N];
set < int > S[N], B[N];
bitset < N > M;
inline bool Check(int id, int val)
{
    if (M[val])
        return (1);
    while (id)
    {
        if (B[id].count(val))
            return (1);
        id >>= 1;
    }
    return (0);
}
inline bool Sub(int id, int pr)
{
    while (id)
    {
        if (id == pr)
            return (1);
        id >>= 1;
    }
    return (0);
}
int main()
{
    scanf("%d", &n);
    memset(A, 1, sizeof(A));
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]), S[i].insert(A[i]), rev[A[i]] = i;
    for (int i = 1; i <= n; i++)
    {
        int lc = i * 2, rc = lc + 1;
        int best = *S[i].begin();
        while (Check(i, best))
        {
            S[i].erase(S[i].begin());
            assert(S[i].size() != 0);
            best = *S[i].begin();
        }
        if (best < A[lc] && best < A[rc])
        {
            R[i] = best;
            M[best] = 1;
            if (Sub(i, rev[best]))
            {
                int pr = rev[best], id = i;
                while (id > pr)
                {
                    for (auto X : S[(id >> 1)])
                        B[id^1].insert(X);
                    B[id].insert(A[id ^1]);
                    id >>= 1;
                    S[id].clear();
                }
            }
            else
            {
                int pr = rev[best];
                B[pr].insert(A[pr]);
                for (auto X : S[(pr >> 1)])
                    B[pr^1].insert(X);
                int id = i;
                pr ^= 1;
                while (id > pr)
                {
                    for (auto X : S[(id >> 1)])
                        B[id^1].insert(X);
                    B[id].insert(A[id ^1]);
                    id >>= 1;
                    S[id].clear();
                }
            }
            //S[i].clear();
            continue;
        }
        if (A[lc] < A[rc])
        {
            R[i] = A[lc];
            M[R[i]] = 1;
            S[lc].clear();
            for (auto X : S[i])
                S[lc].insert(X);
            //S[i].clear();
            continue;
        }
        R[i] = A[rc];
        M[R[i]] = 1;
        S[rc].clear();
        S[rc].insert(A[lc]);
        S[lc].insert(A[lc]);
        for (auto X : S[i])
        {
            S[lc].insert(X);
            S[rc].insert(X);
        }
        //S[i].clear();
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", R[i]);
}

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
swap.cpp:35:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]), S[i].insert(A[i]), rev[A[i]] = i;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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