Submission #98337

#	Time	Username	Problem	Language	Result	Execution time	Memory
98337		Kastanda	Swap (BOI16_swap)	C++11	0 / 100	33 ms	25464 KiB

swap

// * Sigh *
#include<bits/stdc++.h>
using namespace std;
const int N = 400005;
int n, A[N], M[N], H[N];
vector < int > S[N];
inline bool CMP(int i, int j)
{
    return (A[i] > A[j]);
}
inline bool Sub(int i, int j)
{
    return ((i >> (H[i] - H[j])) == j);
}
inline bool Check(int i, int val)
{
    return (Sub(i, M[val]));
}
int main()
{
    scanf("%d", &n);
    memset(A, 63, sizeof(A));
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]),
        S[i].push_back(i);
    for (int i = 1; i < N; i++)
        H[i] = H[i >> 1] + 1;
    for (int i = 1; i <= n; i++)
    {
        int lc = i << 1, rc = lc ^ 1;
        sort(S[i].begin(), S[i].end(), CMP);
        while (!Check(i, A[S[i].back()]))
            S[i].pop_back();
        printf("%d ", min({A[S[i].back()], A[lc], A[rc]}));
        M[min({A[S[i].back()], A[lc], A[rc]})] = n + 1;
        if (A[S[i].back()] < min(A[lc], A[rc]))
        {
            int id = S[i].back(), nw = i;
            if (!Sub(i, id))
            {
                int p = id >> 1;
                for (int a : S[p])
                    M[a] = max(M[a], id);
                S[p].clear();
                id ^= 1;
            }
            while (nw > id)
            {
                int p = nw >> 1;
                for (int a : S[p])
                    M[a] = max(M[a], nw);
                M[A[nw^1]] = min(M[A[nw^1]], nw ^ 1);
                S[p].clear(); nw >>= 1;
            }
        }
        else if (A[lc] < A[rc])
            S[lc] = S[i];
        else
        {
            S[lc] = S[rc] = S[i];
            S[lc].push_back(lc);
            S[rc].push_back(lc);
        }
    }
    return 0;
}

Compilation message (stderr)

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

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