Submission #1269076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269076		binminh01	Longest beautiful sequence (IZhO17_subsequence)	C++20	40 / 100	6090 ms	2004 KiB

subsequence

#include<bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt,tune=native")

#include<stdio.h>
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
constexpr int N = 100000;
int n, m, a[N], b[N], c[N], f[N], g[N];
int main() {
    scan(n);
    for (int i = 0; i < n; ++i) {scan(a[i]);}
    for (int i = 0; i < n; ++i) {scan(b[i]);}
    int k = 0;
    for (int i = 0; i < n; ++i) {
        g[i] = -1;
        for (int j = 0; j < i; ++j) if (__builtin_popcount(a[i] & a[j]) == b[i] && f[i] < f[j]) f[i] = f[j], g[i] = j;
        ++f[i];
        if (f[k] < f[i]) k = i;
    }
    printf("%d\n", f[k]);
    for (; ~k; k = g[k]) c[m++] = k;
    for (int i = m - 1; i >= 0; --i) printf("%d ", c[i] + 1);
}

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