Submission #89956

#	Time	Username	Problem	Language	Result	Execution time	Memory
89956		Vardanyan	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	804 ms	11772 KiB

subsequence

// #pragma GCC optimize "-O3"
#include<bits/stdc++.h>
using namespace std;
const int N = 1000*1000+5;
struct elem{
    int val,ind,par;
};
elem ANS[(1<<24)];
int ALL[N];
int PAR[N];
int a[N];
int k[N];
int CNT(int x){
    int ans = 0;
    for(int i = 0;i<22;i++) if((x>>i)&1) ans++;
    return ans;
}
bool have[(1<<21)];
int main()
{
    int n;
    scanf("%d",&n);
    int mx = 0;
    vector<int> bmask;
    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(i == 2){
            cout<<0<<endl;
        }*/
        for(int q = 0;q<bmask.size();q++){
            int mask = bmask[q];
            int now = mask&a[i];
            if(CNT(now) == k[i]){
                if(ANS[a[i]].val<=ANS[mask].val+1){
                    int x =ANS[mask].ind;
                    int y = ANS[mask].val+1;
                    if(i == x) continue;
                    PAR[i] = x;
                    ANS[a[i]].val = y;
                    ANS[a[i]].par = x;
                    ANS[a[i]].ind = i;
                    ALL[i] = ANS[a[i]].val;
                    if(mx_ans<=ANS[a[i]].val){
                        mx_ans = ANS[a[i]].val;
                        pos = i;
                    }
                }
            }
        }
        if(ANS[a[i]].val == 0){
            ANS[a[i]].val = 1;
            ANS[a[i]].ind = i;
            ALL[i] = 1;
            if(mx_ans<1){
                mx_ans = 1;
                pos = i;
            }
        }
        if(!have[a[i]]){
            have[a[i]] = 1;
            bmask.push_back(a[i]);
        }
    }
    vector<int> ans;
    cout<<mx_ans<<endl;
    while(mx_ans--){
      //  cout<<ANS[pos].ind<<" ";
        ans.push_back(pos);
        pos = PAR[pos];
    }
    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:36:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int q = 0;q<bmask.size();q++){
                       ~^~~~~~~~~~~~~
subsequence.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<ans.size();i++) cout<<ans[i]<<" ";
                   ~^~~~~~~~~~~
subsequence.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
subsequence.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a[i]);
             ~~~~~^~~~~~~~~~~~
subsequence.cpp:29: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: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60