Submission #793068

#TimeUsernameProblemLanguageResultExecution timeMemory
793068Peter2017Longest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> #define fi first #define se second #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define pill pair<int,ll> #define mem(a, b) memset(a, b, sizeof(a)) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) using namespace std; const int N = 1e5 + 5; const int mod = 1e9 + 7; template <typename T1, typename T2> bool maxi(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;} template <typename T1, typename T2> bool mini(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;} int n; int trace[N]; int a[N], k[N]; int f[N], saveTrace[N]; void load(){ cin.tie(0)->sync_with_stdio(0); // freopen("test.inp", "r", stdin); // freopen("test.out", "w", stdout); } void input(){ cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> k[i]; } void get_trace(int i){ if (trace[i] == 0){ cout << i << ' '; return; } get_trace(trace[i]); cout << i << ' '; } void sub2(){ int ans = 0, id = 1; for (int i = 1; i <= n; i++){ f[i] = 1; for (int j = 1; j < i; j++) if (__builtin_popcount(a[i] & a[j]) == k[f[j] + 1]) if (maxi(f[i], f[j] + 1)) trace[i] = j; if (maxi(ans, f[i])) id = i; } cout << ans << '\n'; get_trace(id); } void solve(){ int ans = 0, id = 1; for (int i = 1; i <= n; i++){ int Max = f[i]; for (int mask = 0; mask < MASK(8); mask++){ if (__builtin_popcount(a[i] & mask) == k[f[mask] + 1]){ if (maxi(Max, f[mask] + 1)){ trace[i] = saveTrace[mask]; saveTrace[a[i]] = i; } } } f[i] = Max; if (!f[a[i]]) f[a[i]] = 1, saveTrace[a[i]] = i; if (maxi(ans, f[a[i]])) id = i; } cout << ans << '\n'; get_trace(id); } int main(){ load(); input(); if (n <= 5000) sub2(); else solve(); } /* 4 1 2 3 4 10 0 1 0 5 5 3 5 3 5 10 1 20 1 20 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...