제출 #89947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89947		Vardanyan	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	385 ms	836 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;
}
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 = i;
            ALL[i] = 1;
            if(mx_ans<1){
                mx_ans = 1;
                pos = 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){
                    PAR[i] = ANS[mask].ind;
                    ANS[a[i]].val = ANS[mask].val+1;
                    ANS[a[i]].par = ANS[mask].ind;
                    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;
                    }
                }
            }
        }
    }
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

subsequence.cpp: In function 'int main()':
subsequence.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<ans.size();i++) cout<<ans[i]<<" ";
                   ~^~~~~~~~~~~
subsequence.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
subsequence.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a[i]);
             ~~~~~^~~~~~~~~~~~
subsequence.cpp:27: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