oj.uz

Submission #98336

# Submission time Handle Problem Language Result Execution time Memory
98336 2019-02-22T14:25:57 Z Kastanda Swap (BOI16_swap) C++11
0 / 100
 32 ms 25600 KB 
// * 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);
                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

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

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12928 KB Output is correct
2 Correct 15 ms 12800 KB Output is correct
3 Runtime error 32 ms 25600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12928 KB Output is correct
2 Correct 15 ms 12800 KB Output is correct
3 Runtime error 32 ms 25600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12928 KB Output is correct
2 Correct 15 ms 12800 KB Output is correct
3 Runtime error 32 ms 25600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12928 KB Output is correct
2 Correct 15 ms 12800 KB Output is correct
3 Runtime error 32 ms 25600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12928 KB Output is correct
2 Correct 15 ms 12800 KB Output is correct
3 Runtime error 32 ms 25600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -