제출 #1128058

#제출 시각아이디문제언어결과실행 시간메모리
1128058Noproblem29Longest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
1 ms328 KiB
#include<bits/stdc++.h> using namespace std; #ifndef BADGNU #pragma GCC target("sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #endif #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ll long long #define int ll #define ld long double #define y1 cheza mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; template<class T> using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>; const int N=1e5+100; const int M=5001; const int B=447; const int mod=998244353; const ll INF=1e18; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; const double eps=1e-6; int n; int a[N]; int b[N]; int p[N]; int dp[N]; int last[(1ll<<10ll)]; void test(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ cin>>b[i]; p[i]=i; } int mx=0; for(int i=1;i<=n;i++){ dp[i]=1; for(int j=0;j<(1<<10);j++){ int cur=__builtin_popcountll(a[i]&j); cur-=b[i]; if(cur!=0||last[j]==0)continue; if(dp[i]<dp[last[j]]+1){ dp[i]=dp[last[j]]+1; p[i]=last[j]; } } if(mx==0||dp[mx]<dp[i]){ mx=i; } if(last[a[i]]==0||dp[last[a[i]]]<dp[i]){ last[a[i]]=i; } } cout<<dp[mx]<<'\n'; vector<int>v; v.push_back(mx); while(mx!=p[mx]){ mx=p[mx]; v.push_back(mx); } reverse(v.begin(),v.end()); for(auto i:v){ cout<<i<<' '; } cout<<'\n'; } /* */ signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr); int t2=1; // cin>>t2; for(int i=1;i<=t2;i++){ test(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...