Submission #89943

#	Time	Username	Problem	Language	Result	Execution time	Memory
89943		Vardanyan	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	435 ms	263168 KiB

subsequence

// #pragma GCC optimize "-O3"
#include<bits/stdc++.h>
using namespace std;
const int N = 1000*100+5;
struct elem{
    int val,ind,par;
};
elem ANS[(1<<22)];
int a[N];
int k[N];
int CNT(int x){
    int ans = 0;
    for(int i = 0;i<21;i++) if((x>>i)&1) ans++;
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    int mx = 0;
    for(int i = 1;i<=n;i++){
            scanf("%d",&a[i]);
            mx = max(mx,a[i]);
    }
    for(int i = 1;i<=n;i++) scanf("%d",&k[i]);
    int mx_ans = 0;
    int pos = 0;
    for(int i = 1;i<=n;i++){
        if(ANS[a[i]].val == 0){
            ANS[a[i]].val = 1;
            ANS[a[i]].ind = 1;
            if(mx_ans<1){
                mx_ans = 1;
                pos = a[i];
            }
        }
        for(int mask = 0;mask<=mx;mask++){
            int now = mask&a[i];
            if(CNT(now) == k[i]){
                if(ANS[a[i]].val<ANS[mask].val+1){
                    ANS[a[i]].val = ANS[mask].val+1;
                    ANS[a[i]].ind = i;
                    ANS[a[i]].par = mask;
                    if(mx_ans<ANS[a[i]].val){
                        mx_ans = ANS[a[i]].val;
                        pos = a[i];
                    }
                }
            }
        }
    }
    vector<int> ans;
    cout<<mx_ans<<endl;
    while(ANS[pos].ind!=0){
      //  cout<<ANS[pos].ind<<" ";
        ans.push_back(ANS[pos].ind);
        pos = ANS[pos].par;
    }
    reverse(ans.begin(),ans.end());
    for(int i = 0;i<ans.size();i++) cout<<ans[i]<<" ";
    cout<<endl;
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<ans.size();i++) cout<<ans[i]<<" ";
                   ~^~~~~~~~~~~
subsequence.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
subsequence.cpp:22:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a[i]);
             ~~~~~^~~~~~~~~~~~
subsequence.cpp:25:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1;i<=n;i++) scanf("%d",&k[i]);
                             ~~~~~^~~~~~~~~~~~

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