Submission #1088825

#TimeUsernameProblemLanguageResultExecution timeMemory
1088825LucasLeLongest beautiful sequence (IZhO17_subsequence)C++17
100 / 100
4325 ms255064 KiB
#include <bits/stdc++.h> #define int long long #define moony long long #define pii pair<int, int> #define fi first #define se second #define ld long double #define vi vector<int> #define vii vector<vector<int>> #define all(v) (v).begin(), (v).end() #define rep(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define per(i, b, a) for (int i = (b), _a = (a); i >= _a; --i) using namespace std; const int MOD = 1e9 + 7; int add(int a, int b) { a += b; if (a >= MOD) a -= MOD; return a; } int mul(int a, int b) { (a *= b) %= MOD; return a; } int ceil(int x, int y) { return (x + y - 1) / y; } int bin_pow(int x, int y) { int res = 1; while (y) { if (y & 1) res = res * x % MOD; x = x * x % MOD; y >>= 1; } return res; } template<class T> bool minimize(T& a, T b) { if (a > b) return a = b, true; return false; } template<class T> bool maximize(T& a, T b) { if (a < b) return a = b, true; return false; } const int INF = 1e17; const int maxn = 2e6 + 5; const int B = 10; int n, len, pos; int a[maxn + 5], k[maxn + 5]; int f[maxn + 5], trace[maxn + 5]; pair<int, int> f_mx[1050][1050][15]; int same(int x, int y) { int nx = (x & y); return __builtin_popcountll(nx); } void solve(int tc) { cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) cin >> k[i]; for (int mask = 0; mask < (1ll << B); ++mask) for (int nmask = 0; nmask < (1ll << B); ++nmask) for (int k = 0; k <= B; ++k) f_mx[mask][nmask][k] = make_pair(-1, -1); for (int i = 0; i < n; ++i) { int left_bit = a[i] >> B; int right_bit = a[i] % (1ll << B); f[i] = 1; trace[i] = i; for (int mask = 0; mask < (1ll << B); ++mask) { int need = k[i] - same(mask, left_bit); if (need < 0 || need > B) continue; if (maximize(f[i], f_mx[mask][right_bit][need].first + 1)) { trace[i] = f_mx[mask][right_bit][need].second; } } for (int mask = 0; mask < (1ll << B); ++mask) { int delta = same(mask, right_bit); if (maximize(f_mx[left_bit][mask][delta].first, f[i])) { f_mx[left_bit][mask][delta].second = i; } } if (maximize(len, f[i])) { pos = i; } } cout << len << '\n'; vector<int> ans; while (true) { ans.push_back(pos + 1); if (trace[pos] == pos) break; pos = trace[pos]; } reverse(ans.begin(), ans.end()); for (int x : ans) cout << x << ' '; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tc = 1; //cin >> tc; for (int i = 1; i <= tc; ++i) { solve(i); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...