Submission #96153

#	Time	Username	Problem	Language	Result	Execution time	Memory
96153		choikiwon	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5216 ms	187616 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MN = 100010;

int bcnt[1 << 20];

int N;
int A[MN], B[MN], pre[MN];
pii cnt[1 << 10][1 << 10][22];

void add(int v, int t, int id) {
    int a = v % (1 << 10);
    int b = v / (1 << 10);

    for(int i = 0; i < (1 << 10); i++) {
        cnt[a][i][ bcnt[b & i] ] = max(cnt[a][i][ bcnt[b & i] ], pii(t, id));
    }
}

int main() {
    for(int i = 1; i < (1 << 20); i++) {
        for(int j = 0; j < 20; j++) {
            if(i & (1 << j)) bcnt[i]++;
        }
    }

    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    for(int i = 0; i < N; i++) {
        scanf("%d", &B[i]);
    }

    int ans = 0, la = -1;
    for(int i = 0; i < N; i++) {
        int t = 0, p = -1;
        for(int j = 0; j < (1 << 10); j++) {
            int r = B[i] - bcnt[ A[i] & j ];
            if(r < 0) continue;
            pii d = cnt[j][ A[i] / (1 << 10) ][r];
            if(t < d.first + 1) {
                t = d.first + 1;
                p = d.second;
            }
        }
        add(A[i], t, i);
        pre[i] = p;
        if(ans < t) {
            ans = t;
            la = i;
        }
    }

    printf("%d\n", ans);

    vector<int> sol;
    for(int i = 0; i < ans; i++) {
        sol.push_back(la);
        la = pre[la];
    }
    for(int i = (int)sol.size() - 1; i >= 0; i--) {
        printf("%d ", sol[i] + 1);
    }
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
subsequence.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
subsequence.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &B[i]);
         ~~~~~^~~~~~~~~~~~~

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