Submission #895734

#	Time	Username	Problem	Language	Result	Execution time	Memory
895734		Neco_arc	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	1116 KiB

subsequence

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define getbit(x,i) ((x >> i)&1)
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 1e5 + 7

using namespace std;

int n;
int dp[maxn], a[maxn];
int L[(1 << 10) + 1][(1 << 10) + 1][11];
int p[maxn];

void Trace_Back(int id)
{
    vector<int> ans = {id};
    int pre = id;
    fid(i, id - 1, 1)
    {
        if(cntbit(a[i] & a[pre]) == p[pre] && (dp[i] == dp[pre] - 1)){
            ans.push_back(i);
            pre = i;
        }
    }

    fid(i, ans.size() - 1, 0) cout << ans[i] << " ";
    exit(0);
}

tuple<int, int> dcm(int x)
{
    int l = 0, r = 0;
    fi(i, 1, 10) if(getbit(x, i - 1)) l |= (1 << (i - 1));
    fi(i, 11, 20) if(getbit(x, i - 1)) r |= (1 << (i - 10 - 1));
    return {l, r};
}

int main()
{

    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    fi(i, 1, n) cin >> a[i];
    fi(i, 1, n) cin >> p[i];

    int ans = 0;
    fi(i, 1, n)
    {
        dp[i] = 1;
        int Left, Right;
        tie(Left, Right) = dcm(a[i]);

        fi(l, 0, (1 << 10) - 1) dp[i] = max(dp[i], L[l][Right][p[i] - cntbit(l & Left)] + 1);
        fi(r, 0, (1 << 10) - 1) L[Left][r][cntbit(r & Right)] = max(L[Left][r][cntbit(r & Right)], dp[i]);

        ans = max(ans, dp[i]);
    }

    cout << ans << '\n';

    fi(i, 1, n) if(dp[i] == ans) Trace_Back(i);

    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'std::tuple<int, int> dcm(int)':
subsequence.cpp:37:33: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   37 |     fi(i, 1, 10) if(getbit(x, i - 1)) l |= (1 << (i - 1));
      |                               ~~^~~
subsequence.cpp:5:28: note: in definition of macro 'getbit'
    5 | #define getbit(x,i) ((x >> i)&1)
      |                            ^
subsequence.cpp:38:34: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   38 |     fi(i, 11, 20) if(getbit(x, i - 1)) r |= (1 << (i - 10 - 1));
      |                                ~~^~~
subsequence.cpp:5:28: note: in definition of macro 'getbit'
    5 | #define getbit(x,i) ((x >> i)&1)
      |                            ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60