Submission #1101154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101154		MateiKing80	Swap (BOI16_swap)	C++14	100 / 100	510 ms	233896 KiB

swap

#include <bits/stdc++.h>

using namespace std;

int a[200002];
bool nevoie[200002][18][2];
vector<int> dp[200002][18][2], sus, sus2;

void mrg(vector<int> &ret, vector<int> &l, vector<int> &r)
{
    for(int i = 0, j = 1; i < l.size(); i += j, j <<= 1)
    {
        for(int k = i; k < i + j && k < l.size(); k ++)
            ret.push_back(l[k]);
        for(int k = i; k < i + j && k < r.size(); k ++)
            ret.push_back(r[k]);
    }
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    nevoie[1][0][1] = 1;
    for(int nod = 1; nod <= n / 2; nod ++)
        for(int i = 0; nod >> i; i ++)
            for(int j :{0, 1})
            {
                if(!nevoie[nod][i][j])
                    continue;
                int mn = min({a[((nod >> i + 1) << 1) + j], a[2 * nod], a[2 * nod + 1]});
                if(mn == a[((nod >> i + 1) << 1) + j])
                    nevoie[2 * nod][0][0] = nevoie[2 * nod + 1][0][1] = 1;
                else if(mn == a[2 * nod])
                    nevoie[2 * nod][i + 1][j] = nevoie[2 * nod + 1][0][1] = 1;
                else
                {
                    nevoie[2 * nod][0][0] = nevoie[2 * nod][i + 1][j] = 1;
                    nevoie[2 * nod + 1][0][0] = nevoie[2 * nod + 1][i + 1][j] = 1;
                }
            }
    for(int nod = n; nod; nod --)
    {
        for(int i = 0; nod >> i; i ++)
            for(int j = 0; j < 2; j ++)
            {
                if(!nevoie[nod][i][j])
                    continue;
                int p = ((nod >> i + 1) << 1) + j;
                if(2 * nod > n)
                    dp[nod][i][j] = {a[p]};
                else if(2 * nod == n)
                    dp[nod][i][j] = {min(a[p], a[2 * nod]), max(a[p], a[2 * nod])};
                else if(a[2 * nod + 1] < min(a[p], a[2 * nod]))
                {
                    sus = sus2 = {a[2 * nod + 1]};
                    mrg(sus, dp[2 * nod][0][0], dp[2 * nod + 1][i + 1][j]);
                    mrg(sus2, dp[2 * nod][i + 1][j], dp[2 * nod + 1][0][0]);
                    dp[nod][i][j] = min(sus, sus2);
                }
                else
                {
                    dp[nod][i][j] = {min(a[p], a[2 * nod])};
                    if(a[p] < a[2 * nod])
                        mrg(dp[nod][i][j], dp[2 * nod][0][0], dp[2 * nod + 1][0][1]);
                    else
                        mrg(dp[nod][i][j], dp[2 * nod][i + 1][j], dp[2 * nod + 1][0][1]);
                }
            }
        if(2 * nod < n)
            for(int i = 0; 2 * nod >> i; i ++)
                for(int j = 0; j < 2; j ++)
                {
                    vector<int>().swap(dp[2 * nod][i][j]);
                    vector<int>().swap(dp[2 * nod + 1][i][j]);
                }
    }
    for(int i : dp[1][0][1])
        cout << i << " ";
    return 0;
}

Compilation message (stderr)

swap.cpp: In function 'void mrg(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:11:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0, j = 1; i < l.size(); i += j, j <<= 1)
      |                           ~~^~~~~~~~~~
swap.cpp:13:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         for(int k = i; k < i + j && k < l.size(); k ++)
      |                                     ~~^~~~~~~~~~
swap.cpp:15:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for(int k = i; k < i + j && k < r.size(); k ++)
      |                                     ~~^~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:33:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |                 int mn = min({a[((nod >> i + 1) << 1) + j], a[2 * nod], a[2 * nod + 1]});
      |                                          ~~^~~
swap.cpp:34:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |                 if(mn == a[((nod >> i + 1) << 1) + j])
      |                                     ~~^~~
swap.cpp:51:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |                 int p = ((nod >> i + 1) << 1) + j;
      |                                  ~~^~~

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