Submission #367563

#	Time	Username	Problem	Language	Result	Execution time	Memory
367563		mohamedsobhi777	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3865 ms	93264 KiB

subsequence

#include <bits/stdc++.h>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

using namespace std;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)

using ll = long long;
using ld = long double;

const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const int M = (1 << 10);

int n;
int cnt[M * M];
int dp[M][M][21];
int ans[N];
vi a, b;

bool chk(int i, int j)
{
       return __builtin_popcount((a[i] & a[j])) == b[j];
}

void solve(int ix)
{
       for (int i = ix - 1; ~i; --i)
       {
              if (chk(i, ix) && ans[i] + 1 == ans[ix])
              {
                     solve(i);
                     break;
              }
       }
       cout << ix + 1 << " ";
}

pii num(int x)
{
       return {x >> 10, x % (1 << 10)};
}

void out(int x)
{
       for (int i = 9; ~i; --i)
       {
              cout << !!(x & (1 << i));
       }
       cout << " ";
}

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n;
       a.resize(n), b.resize(n);
       for (auto &u : a)
              cin >> u;
       for (auto &u : b)
              cin >> u;
       for (int i = 1; i < M * M; ++i)
              cnt[i] = __builtin_popcount(i);

       int mx = 0, ix = 0;
       for (int i = 0; i < n; ++i)
       {
              pii x = num(a[i]);
              int ret = 1;
              for (int j = 0; j < (1 << 10); ++j)
              {
                     int sh1 = __builtin_popcount((x.f & j));
                     int rem = b[i] - sh1;
                     if (sh1 > b[i] || rem > 10)
                     {
                            continue;
                     }
                     ret = max(ret, dp[j][x.s][rem] + 1);
              }
              for (int j = 0; j < M; ++j)
              {
                     int sh2 = __builtin_popcount((j & x.s));
                     dp[x.f][j][sh2] = max(dp[x.f][j][sh2], ret);
              }
              if (ret > mx)
              {
                     mx = ret;
                     ix = i;
              }
              ans[i] = ret;
       }
       cout << mx << "\n";
       solve(ix);
       return 0;
}

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