Submission #781239

#	Time	Username	Problem	Language	Result	Execution time	Memory
781239		vgoofficial	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	49 ms	1620 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 1000000007;
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    int n;
    cin >> n;
    int a[n], k[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> k[i];
    if(n<=5000) {
        vector<ll> longestEnd(n, 1); //longestEnd[a]=b: ends at index a, longest = b.
        vector<int> prev(n, -1);
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(__builtin_popcountll(a[i]&a[j])==k[i]) {
                    if(longestEnd[j]+1>longestEnd[i]) {
                        longestEnd[i]=longestEnd[j]+1;
                        prev[i]=j;
                    }
                }
            }
        }
        int bestIndex = 0;
        int most = longestEnd[0];
        for(int i = 1; i < n; i++) {
            if(longestEnd[i]>most) {
                most=longestEnd[i];
                bestIndex=i;
            }
        }
        string ans = to_string(1+bestIndex);
        while(prev[bestIndex]!=-1) {
            bestIndex=prev[bestIndex];
            ans=to_string(1+bestIndex)+" "+ans;
        }
        cout << most << endl << ans << endl;
    }
}
/*
4
1 2 3 4
10 0 1 0
*/

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