제출 #92727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92727		toloraia	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	512 ms	263168 KiB

subsequence

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

const int N = 1e6 + 5;

int n;
int a[N], b[N];
int dp[N], w[N];
int B[N];
int D[N], d[N];
vector < int > V;

int main()
{
    cin>>n;
    for (int i = 1; i <= n; i++)
        cin>>a[i];
    for (int i = 1; i <= n; i++)
        cin>>b[i];
    B[0] = 0;
    for (int i = 1; i < (1<<20); i++)
        B[i] = 1 + B[(i & (i - 1))];
    dp[1] = 1;
    D[a[1]] = 1;
    for (int i = 2; i <= n; i++){
        if (n <= 5000){
            for (int j = 1; j < i; j++)
                if (B[(a[i] & a[j])] == b[i])
                    if (dp[i] < dp[j]){
                        dp[i] = dp[j];
                        w[i] = j;
                    }
        }
        else {
            for (int j = 0; j < (1<<8); j++)
                if (B[a[i] & j] == b[i])
                    if (dp[i] < D[j]){
                        dp[i] = D[j];
                        w[i] = d[j];
                    }
        }
        dp[i]++;
        if (D[a[i]] < dp[i]){
            D[a[i]] = dp[i];
            d[a[i]] = i;
        }
    }
    int x = 1;
    for (int i = 2; i <= n; i++)
        if (dp[i] > dp[x])
            x = i;
    cout<<dp[x]<<endl;
    while (x){
        V.push_back(x);
        x = w[x];
    }
    for (int i = (int)V.size() - 1; i >= 0; i--)
        cout<<V[i]<<" ";
    cout<<endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

subsequence.cpp: In function 'int main()':
subsequence.cpp:22:14: warning: iteration 1000004 invokes undefined behavior [-Waggressive-loop-optimizations]
         B[i] = 1 + B[(i & (i - 1))];
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:21:23: note: within this loop
     for (int i = 1; i < (1<<20); i++)
                     ~~^~~~~~~~~

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