Submission #1006661

#TimeUsernameProblemLanguageResultExecution timeMemory
1006661emad234Longest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
38 ms10588 KiB
#include "bits/stdc++.h" #define F first #define S second #define ll long long #define pii pair<ll,ll> const ll mxN = 5e5 + 5; const ll mod = 1e9 + 7; using namespace std; int a[mxN],b[mxN]; int dp[mxN]; int opt[mxN],opid[mxN]; vector<int>op[256]; int prv[mxN]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; for(int i = 1;i <= n;i++){ cin >>a[i]; } for(int i = 1;i <= n;i++){ cin >>b[i]; } if(n > 5000){ for(int i = 0;i <= 256;i++){ for(int x = 0;x <= 256;x++){ if(__builtin_popcount(a[i] & x) == b[i]) op[i].push_back(x); } } } int ans = 1; int mxid = 1; dp[1] = 1; if(n > 5000){ opt[a[1]] = 1; opid[a[1]] = 1; for(int i = 2;i <= n;i++){ dp[i] = 1; for(auto x : op[a[i]]){ if(opt[x] > dp[i]){ dp[i] = opt[x] + 1; prv[i] = opid[x]; } } if(opt[a[i]] < dp[i]){ opt[a[i]] = dp[i]; opid[a[i]] = i; } if(dp[i] > ans){ ans = dp[i]; mxid = i; } } }else{ for(int i = 2;i <= n;i++){ dp[i] = 1; for(int j = 1;j < i;j++){ if(__builtin_popcount(a[i] & a[j]) == b[i]) { if(dp[j] + 1 > dp[i]){ dp[i] = dp[j] + 1; prv[i] = j; } } } if(dp[i] > ans){ ans = dp[i]; mxid = i; } } } cout<< ans<<'\n'; vector<int>v; while(mxid){ v.push_back(mxid); mxid = prv[mxid]; } reverse(v.begin(),v.end()); for(auto x : v) cout<<x<<' '; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...