Submission #367544

#	Time	Username	Problem	Language	Result	Execution time	Memory
367544		mohamedsobhi777	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	1 ms	364 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 trio[N * 10][2];
pii vs[N * 20];
int T;

void add(int x, int v, int j)
{
       int cur = 0;
       for (int i = 19; ~i; --i)
       {
              bool flag = !!(x & (1 << i));
              if (!trio[cur][flag])
              {
                     trio[cur][flag] = ++T;
              }
              cur = trio[cur][flag];
       }
       vs[cur] = max(vs[cur], make_pair(v, j));
}

pii query(int v, int k, int x = 0, int j = 19)
{
       if (k < 0)
              return {-1e9, 0};

       if (j == -1)
       {
              if (!k)
                     return vs[x];
              else
                     return {-1e9, 0};
       }
       bool flag = !!(v & (1 << j));
       pii ret = {-1e9, 0};
       for (int i = 0; i < 2; ++i)
       {
              if (trio[x][i])
              {
                     ret = max(ret, query(v, k - (flag == i && i), trio[x][i], j - 1));
              }
       }
       return ret;
}

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);
       dp[0] = 1;
       add(a[0], 1, 0);
       for (int i = 1; i < n; ++i)
       {
              pii q = query(a[i], b[i]);
              dp[i] = q.f + 1;
              prv[i] = q.s;
              add(a[i], dp[i], i);
       }

       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: 0 / 7
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60