제출 #1102530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102530		dead0ne	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5197 ms	183348 KiB

subsequence

#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
//#define int long long
#define ii pair<long long,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define mid (l+r)/2
#define inf 1e15
#define MOD 1000000007
#define MX 1505
using namespace std;

ii dp[1<<10][1<<10][11];

void solve(){
    int n; cin >> n;
    int a[n], k[n];
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=0; i<n; i++) cin >> k[i];
    for(int i=0; i<1<<10; i++) for(int j=0; j<1<<10; j++) for(int k=0; k<=10; k++) dp[i][j][k]={0, -1};
    int ans=0, bestie=0;
    int pre[n];
    memset(pre, -1, sizeof(pre));
    for(int i=0; i<n; i++){
        ii cur={a[i]>>10, a[i]&((1<<10)-1)};
        int res=1;
        for(int j=0; j<1<<10; j++){
            if(k[i]-__builtin_popcount(cur.st&j)>10 || k[i]-__builtin_popcount(cur.st&j)<0) continue;
            if(dp[j][cur.nd][k[i]-__builtin_popcount(cur.st&j)].st+1>res){
                res = dp[j][cur.nd][k[i]-__builtin_popcount(cur.st&j)].st+1;
                pre[i] = dp[j][cur.nd][k[i]-__builtin_popcount(cur.st&j)].nd;
            }
        }
        if(res>ans){
            ans=res;
            bestie=i;
        }
        for(int j=0; j<1<<10; j++){
            if(res > dp[cur.st][j][__builtin_popcount(cur.nd&j)].st){
                dp[cur.st][j][__builtin_popcount(cur.nd&j)].st = res;
                dp[cur.st][j][__builtin_popcount(cur.nd&j)].nd = i;
            }
        }
    }
    cout << ans << endl;
    vi wow;
    while(bestie>-1){
        wow.pb(bestie);
        bestie=pre[bestie];
    }
    for(int i=wow.size()-1; i>=0; i--){
        if(i<wow.size()-1) cerr << wow[i+1]+1 spc wow[i]+1 spc __builtin_popcount(a[wow[i+1]]&a[wow[i]]) spc k[wow[i]] << endl;
        cout << wow[i]+1 << " ";
    }
}

 
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    #ifdef Local
    freopen("in","r",stdin);
    freopen("out","w",stdout);
    #endif
 
    /*freopen(".in","r",stdin);
    freopen(".out","w",stdout);*/

    int t=1;
    //cin >> t;
    while(t--) solve();
}

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

subsequence.cpp: In function 'void solve()':
subsequence.cpp:59:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         if(i<wow.size()-1) cerr << wow[i+1]+1 spc wow[i]+1 spc __builtin_popcount(a[wow[i+1]]&a[wow[i]]) spc k[wow[i]] << endl;
      |            ~^~~~~~~~~~~~~

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