Submission #38260

#	Time	Username	Problem	Language	Result	Execution time	Memory
38260		Talant	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	193 ms	3968 KiB

subsequence

#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const int inf = (int)1e9 + 7;
const int N = (int)1e5 + 7;

int n;
int a[N],b[N],p[N],dp[N],u[N];
int mx,id;

int main () {
        cin >> n;

        for (int i = 1; i <= n; i ++)
                cin >> a[i];

        for (int i = 1; i <= n; i ++)
                cin >> b[i];

        if (n <= 5000) {
                for (int i = 1; i <= n; i ++) {
                        dp[i] = 1;
                        p[i] = -1;
                        for (int j = 1; j < i; j ++) {
                                if (__builtin_popcount(a[j] & a[i]) == b[i] && dp[i] < dp[j] + 1)
                                        dp[i] = dp[j] + 1,p[i] = j;
                        }
                        if (mx < dp[i])
                                mx = dp[i],id = i;
                }
                cout << dp[id] << endl;

                deque <int> dq;

                while (id != -1) {
                        dq.push_front(id);
                        id = p[id];
                }
                for (int i = 0; i < dq.size(); i ++)
                        cout << dq[i] << " ";
        }
        else {
                for (int i = 1; i <= n; i ++) {
                        dp[i] = 1;
                        p[i] = -1;
                        for (int j = 0; j <= 256; j ++) {
                                if (__builtin_popcount(j & a[i]) == b[i]) {

                                        if (dp[i] < dp[u[j]] + 1)
                                                dp[i] = dp[u[j]] + 1,p[i] = u[j];
                                }
                        }
                        if (dp[u[a[i]]] < dp[i])
                                u[a[i]] = i;

                        if (u[a[i]] == 0)
                                u[a[i]] = i;

                        if (mx < dp[i])
                                mx = dp[i],id = i;
                }
                cout << dp[id] << endl;

                deque <int> dq;

                while (id != -1) {
                        dq.push_front(id);
                        id = p[id];
                }
                for (int i = 0; i < dq.size(); i ++)
                        cout << dq[i] << " ";
        }
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:48:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int i = 0; i < dq.size(); i ++)
                                   ^
subsequence.cpp:79:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int i = 0; i < dq.size(); i ++)
                                   ^

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