Submission #874177

#	Time	Username	Problem	Language	Result	Execution time	Memory
874177		elotelo966	Longest beautiful sequence (IZhO17_subsequence)	C++17	7 / 100	27 ms	7256 KiB

subsequence

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY 1000000005
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mid (start+end)/2
#define lim 5005
#define se second
#define fi first
vector<int> v[lim];
int vis[lim],uzak[lim],gel[lim];

inline int bul(int x){
    int tut=__builtin_popcount(x);
    return tut;
}

inline void dfs(int node){
    if(vis[node])return ;
    vis[node]=1;
    for(int i=0;i<v[node].size();i++){
        if(uzak[v[node][i]]<uzak[node]+1){
            uzak[v[node][i]]=uzak[node]+1;
            gel[v[node][i]]=node;
        }
        dfs(v[node][i]);
    }
}

int32_t main(){
    faster
    int n;cin>>n;
    int a[n+1],k[n+1];
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>k[i];
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int deg=a[i]&a[j];
            if(bul(deg)==k[j]){
                v[i].push_back(j);
                //v[j].push_back(i);
                //cout<<bul(deg)<<" "<<deg<<" "<<k[j]<<endl;
            }
        }
    }
    vector<int> cev,mm;
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            mm.clear();
            dfs(i);
            int maxi=-1,tut=-1;
            for(int j=1;j<=n;j++){
                if(maxi<uzak[j]){
                    maxi=uzak[j];
                    tut=j;
                }
            }
            //cout<<tut<<" "<<maxi<<endl;
            mm.push_back(tut);
            //cout<<tut<<" "<<gel[tut]<<endl;
            while(gel[tut]!=i && gel[tut]!=0){
                //cout<<tut<<" "<<gel[tut]<<endl;
                tut=gel[tut];
                mm.push_back(tut);
            }
            if(gel[tut]!=0)mm.push_back(gel[tut]);
            if(mm.size()>cev.size()){
                cev=mm;
            }
            memset(gel,0,sizeof(gel));
            memset(uzak,0,sizeof(gel));
        }
    }
    reverse(cev.begin(),cev.end());
    if(cev.size()==1){
        cout<<1<<'\n'<<1<<'\n';
        return 0;
    }
    cout<<cev.size()<<'\n';
    for(auto x:cev)cout<<x<<" ";
    cout<<'\n';
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'void dfs(long long int)':
subsequence.cpp:24:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<v[node].size();i++){
      |                 ~^~~~~~~~~~~~~~~

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