Submission #367527

#	Time	Username	Problem	Language	Result	Execution time	Memory
367527		mohamedsobhi777	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	6029 ms	2540 KiB

subsequence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#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;
using namespace __gnu_pbds;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#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 lll = __int128;
using ll = long long;
using ld = long double;

const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;

auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;

int n;

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif

       cin >> n;
       vi a(n), b(n);
       for (auto &u : a)
              cin >> u;
       for (auto &u : b)
              cin >> u;

       auto ok = [&](int i, int j) -> bool {
              return __builtin_popcount((a[i] & a[j])) == b[j];
       };

       vi dp(n + 1, 0), prv(n + 1, -1);
       for (int i = 0; i < n; ++i)
       {
              dp[i] = 1;
              for (int j = 0; j < i; ++j)
              {
                     if (ok(j, i))
                     {
                            if (dp[j] + 1 > dp[i])
                            {
                                   dp[i] = dp[j] + 1;
                                   prv[i] = j;
                            }
                     }
              }
       }
       int Max = *max_element(all(dp));
       vi ans;
       for (int i = 0; i < n; ++i)
       {
              if (dp[i] == Max)
              {
                     int lst = i;
                     ans.pb(i);
                     for (int j = i - 1; ~j; --j)
                     {
                            if (ok(j, lst) && dp[j] == dp[lst] - 1)
                            {
                                   ans.pb(j);
                                   lst = j;
                            }
                     }
                     break;
              }
       }
       cout << sz(ans) << "\n";
       while (sz(ans))
       {
              cout << ++ans.back() << " ";
              ans.pop_back();
       }
       return 0;
}

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