(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #524100

#TimeUsernameProblemLanguageResultExecution timeMemory
524100NursikLongest beautiful sequence (IZhO17_subsequence)C++14
100 / 100
1946 ms55168 KiB
#include <bits/stdc++.h> #define pb push_back #define ll long long #define ld long double #define f first #define s second #define mp make_pair const ll maxn = 2e6 + 100, maxm = 11, maxk = (1 << 10); const ll inf = 1000000000, mod = inf + 7, mod2 = 998244353; const ll pa = 31, block = 400; using namespace std; int n; int a[maxn], k[maxn], len[maxn], last[maxn], dp[maxk][maxk][maxm], cnt[maxn]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n; for (int i = 1; i <= n; ++i){ cin >> a[i]; } for (int i = 1; i <= n; ++i){ cin >> k[i]; } for (int i = 1; i <= maxn - 1; ++i){ cnt[i] = __builtin_popcount(i); } for (int i = 1; i <= n; ++i){ int f = 0, s = 0; for (int j = 0; j < 10; ++j){ if ((1 << j) & a[i]){ f |= (1 << j); } if ((1 << (j + 10)) & a[i]){ s |= (1 << j); } } len[i] = 1; for (int j = 0; j < maxk; ++j){ int need = k[i] - cnt[j & f]; if (need >= 0 && need < maxm){ int pos = dp[j][s][need]; if (len[pos] + 1 > len[i]){ len[i] = len[pos] + 1; last[i] = pos; } } } for (int j = 0; j < maxk; ++j){ int x = cnt[j & s]; int ind = dp[f][j][x]; if (len[ind] < len[i]){ dp[f][j][x] = i; } } } int pos = 0; for (int i = 1; i <= n; ++i){ if (len[pos] < len[i]){ pos = i; } } vector<int> v; while (pos > 0){ v.pb(pos); pos = last[pos]; } cout << v.size() << '\n'; reverse(v.begin(), v.end()); for (auto it : v){ cout << it << " "; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...