Submission #859775

#	Time	Username	Problem	Language	Result	Execution time	Memory
859775		phongcd	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	3 ms	2396 KiB

subsequence

#include <bits/stdc++.h>
#define ll long long
#define ld long  double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 1e5 + 2;
const ll MOD = 998244353;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 400;
 
int n;
int a[N], b[N];
int cnt[12][12];
ii f[1 << 10 + 2][1 << 10 + 2][12];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    
    for (int i = 0; i < (1 << 10); i ++)
        for (int j = 0; j < (1 << 10); j ++)
            cnt[i][j] = __builtin_popcount(i & j);

    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) cin >> b[i];

    vector <int> trace(n + 1);

    int n1 = n / 2, n2 = n - n1;
    int ans = 1, k = 1;
    for (int i = 1; i <= n; i ++) {
        int l = a[i] & (1ll << n1 - 1);
        int r = a[i] >> n1;
        
        int cur = 1;
        for (int s = 0; s < (1 << n1); s ++) {
            int w = b[i] - cnt[s][l];
            if (0 > w || w > n2) continue;
            if (f[s][r][w].fi + 1 > cur)
                cur = f[s][r][w].fi + 1, trace[i] = f[s][r][w].se;
        }

        if (cur > ans)
            ans = cur, k = i;

        for (int s = 0; s < (1 << n2); s ++) 
            if (f[l][s][cnt[s][r]].fi < cur) 
                f[l][s][cnt[s][r]] = {cur, i};
    }

    cout << ans << '\n';
    vector <int> res;
    while (k > 0) {
        res.push_back(k);
        k = trace[k];
    }
    reverse(all(res));
    for (int u: res) cout << u << ' ';
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

Compilation message (stderr)

subsequence.cpp:22:14: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   22 | ii f[1 << 10 + 2][1 << 10 + 2][12];
      |           ~~~^~~
subsequence.cpp:22:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   22 | ii f[1 << 10 + 2][1 << 10 + 2][12];
      |                        ~~~^~~
subsequence.cpp: In function 'int main()':
subsequence.cpp:41:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   41 |         int l = a[i] & (1ll << n1 - 1);
      |                                ~~~^~~
subsequence.cpp:30:23: warning: iteration 12 invokes undefined behavior [-Waggressive-loop-optimizations]
   30 |             cnt[i][j] = __builtin_popcount(i & j);
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:29:27: note: within this loop
   29 |         for (int j = 0; j < (1 << 10); j ++)
      |                         ~~^~~~~~~~~~~
subsequence.cpp:30:23: warning: iteration 12 invokes undefined behavior [-Waggressive-loop-optimizations]
   30 |             cnt[i][j] = __builtin_popcount(i & j);
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:28:23: note: within this loop
   28 |     for (int i = 0; i < (1 << 10); i ++)
      |                     ~~^~~~~~~~~~~

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