Submission #685962

#TimeUsernameProblemLanguageResultExecution timeMemory
685962dostigatorLongest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
107 ms2516 KiB
#include <bits/stdc++.h> using namespace std; #define all(a) a.begin(),a.end() #define pb push_back #define vt vector #define endl '\n' #define Y second #define X first typedef long long ll; typedef long double ld; const ll mod=1e9+7; const ll INF=1e18; const int inf=1e9; const int N=2e6+505; const int M=3e3+10; const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0}; /*From Benq: stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH*/ int n,a[N],k[N]; int dp[N],pr[N],pos[N]; void solve(){ cin>>n; int bg=0; for(int i=0; i<=256; ++i){ pos[i]=-1; } for(int i=1; i<=n; ++i){ cin>>a[i]; pr[i]=-1; bg=max(bg,a[i]); dp[i]=1; }for(int i=1; i<=n; ++i)cin>>k[i]; if(n<=5000){ int f=1,ps=1; for(int i=1; i<=n; ++i){ for(int j=1; j<i; ++j){ if(__builtin_popcount((a[i]&a[j]))==k[i]){ dp[i]=max(dp[i],dp[j]+1); if(dp[i]==dp[j]+1)pr[i]=j; f=max(f,dp[i]); if(f==dp[i])ps=i; } } }cout<<f<<endl; vt<int>lst; while(ps!=-1){ lst.pb(ps); ps=pr[ps]; }reverse(all(lst)); for(int x:lst)cout<<x<<' '; cout<<endl; return; } if(bg<=256){ int ans=1,r=1; for(int i=1; i<=n; ++i){ for(int x=0; x<=256; ++x){ if(__builtin_popcount(a[i]&x)==k[i] && pos[x]!=-1){ int ps=pos[x]; dp[i]=max(dp[i],dp[ps]+1); if(dp[i]==dp[ps]+1)pr[i]=ps; ans=max(ans,dp[i]); if(ans==dp[i])r=i; } }pos[a[i]]=i; }cout<<ans<<endl; vt<int>lst; while(r!=-1){ lst.pb(r); r=pr[r]; } reverse(all(lst)); for(int x:lst){ cout<<x<<' '; }cout<<endl; return; } } int main(){ //srand(time(0)); //freopen("hotel.in","r",stdin); //freopen("hotel.out","w",stdout); ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int tt=1,lolol=0; // cin>>tt; while(tt--) { //cout<<"Case "<<++lolol<<": "; solve(); } }

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:96:15: warning: unused variable 'lolol' [-Wunused-variable]
   96 |      int tt=1,lolol=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...