Submission #809919

#	Time	Username	Problem	Language	Result	Execution time	Memory
809919		andecaandeci	Longest beautiful sequence (IZhO17_subsequence)	C++17	7 / 100	6043 ms	15660 KiB

subsequence

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define sec second
#define pb push_back
#define int long long
#define pqueue priority_queue
#define pii pair<int,int>
#define supercepat ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
//GA AC GA LAKI
using namespace std;
int tc,n,tp,rt;
int a[100005],k[100005];
vector<int> adj[100005],adj2[100005];
int dis[100005];
int vis[100005];
vector<int> ans;
int day;
void backtrack(int x){
  ans.pb(x);
  for(auto i : adj2[x]){
    if(dis[i]==dis[x]-1){
      backtrack(i);
      break;
    }
  }
}
void dfs(int x){
  vis[x]=day;
  for(auto i : adj[x]){
    dis[i]=max(dis[i],dis[x]+1);
    dfs(i);
  }
}
int biton(int x,int y){
    int temp=x&y;
  int sum=0;
    for(int i=21;i>=0;i--){
      if(pow(2,i)<=temp){
        temp-=pow(2,i);
        sum++;
      }
    }
    return sum;
}
void makegrap(){
  for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
      if(biton(a[i],a[j])==k[j]){
        adj[i].pb(j);
        adj2[j].pb(i);
      }
    }
  }
}
main(){
  supercepat;
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=n;i++) cin>>k[i];
  makegrap();
  day++;
  for(int i=1;i<=n;i++){
    if(vis[i]!=day){
      dis[i]=1;
      dfs(i);
    }
    if(dis[i]>tp) rt=i;
    tp=max(tp,dis[i]);
  }
//  cout<<rt<<endl;
//  for(int i=1;i<=n;i++){
//    cout<<dis[i]<<' ';
//  }
//  cout<<endl;
  backtrack(rt);
  reverse(ans.begin(),ans.end());
  cout<<ans.size()<<endl;
  for(auto i : ans) cout<<i<<" ";
  cout<<endl;
}
/*
vector vec;
for(i=1;i<=n;i++) dp(i,1) vec.pb(i);
dp(x,subl)
untuk suatu index x, cek i dari x+1 sampai n apabila biton(a[i]&a[x])==k[i] -> dp(i,subl+1)
vec.pop()
if(subl>tp) kita copy arraynya
*/

Compilation message (stderr)

subsequence.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main(){
      | ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60