Submission #763936

#TimeUsernameProblemLanguageResultExecution timeMemory
763936AloraLongest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
648 ms5648 KiB
#include <bits/stdc++.h> #define name "cownav" #define fi(i,a,b) for(int i = a; i <= b; i++) #define fid(i,a,b) for(int i = a; i >= b; i--) #define ll long long #define f first #define se second #define pii pair<int, int> #define getbit(i, j) ((i >> j) & 1) #define pb push_back #define all(v) v.begin(), v.end() #define maxn 100005 const int M = 1e9 + 7; using namespace std; int n, a[maxn], k[maxn], res, sl; pii L[maxn]; int ans[maxn]; void sub2(){ fi(i, 2, n) fi(j, 1, i - 1) if(__builtin_popcount(a[i] & a[j]) == k[i]){ L[i] = max(L[i], {L[j].f + 1, j}); res = max(res, L[i].f); } fi(i, 1, n) if(L[i].f == res){ cout << L[i].f + 1 << '\n'; int sl = 0; int x = i; while(x != 0){ ans[++sl] = x; x = L[x].se; } fid(j, sl, 1) cout << ans[j] << " "; exit(0); } } vector <int> pos[1 << 8]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); // freopen(name".in", "r", stdin); // freopen(name".out", "w", stdout); cin >> n; fi(i, 1, n) cin >> a[i]; fi(i, 1, n) cin >> k[i]; if(n <= 5000) sub2(); fi(i, 1, n) pos[a[i]].pb(i); fi(i, 1, n){ fi(x, 0, (1 << 8) - 1) if(__builtin_popcount(a[i] & x) == k[i]){ for(auto j: pos[x]){ if(j > i) break; L[i] = max(L[i], {L[j].f + 1, j}); } res = max(res, L[i].f); } } fi(i, 1, n) if(L[i].f == res){ cout << L[i].f + 1 << '\n'; int x = i; while(x != 0){ ans[++sl] = x; x = L[x].se; } fid(j, sl, 1) cout << ans[j] << " "; return 0; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...