제출 #781250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
781250		vgoofficial	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	6038 ms	3128 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];
    bool over511 = false;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        if(a[i]>511) over511=true;
    }
    for(int i = 0; i < n; i++) cin >> k[i];
    if(over511) {
        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;
    } else {
        vector<int> longest(512, -1);
        vector<ll> longestEnd(n, 1);
        vector<int> prev(n, -1);
        longest[a[0]]=0;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < 512; j++) {
                if(__builtin_popcountll(j&a[i])==k[i]) {
                    if(longest[j]==-1) continue;
                    if(longestEnd[longest[j]]+1>longestEnd[i]) {
                        longestEnd[i]=longestEnd[longest[j]]+1;
                        prev[i]=longest[j];
                    }
                }
            }
            if(longest[a[i]]==-1||longestEnd[i]>longestEnd[longest[a[i]]]) {
                longest[a[i]]=i;
            }
        }
        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: 17 / 17
• Subtask 4: 0 / 60