Submission #883511

#	Time	Username	Problem	Language	Result	Execution time	Memory
883511		skywwla	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	348 KiB

subsequence

#include <bits/stdc++.h>

using namespace std ;
using ll = long long ;

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    int n ; scanf("%d", &n) ;
    vector<int> a(n), k(n), dp(n, 1), pr(n, -1) ;
    for (int &i : a) scanf("%d", &i) ;
    for (int &i : k) scanf("%d", &i) ;
    vector<int> mx((1 << 8) + 1, -1) ;
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < (1 << 8) ; j++) {
            if (mx[j] == -1) continue ;
            int ind = mx[j] ;
            if (dp[ind] + 1 > dp[i] && __builtin_popcount(j & a[i]) == k[i]) {
                dp[i] = dp[ind] + 1 ;
                pr[i] = ind ;
            }
        }
        if (mx[a[i]] == -1 || dp[mx[a[i]]] < dp[i]) {
            mx[a[i]] = i ;
        }
    }
    int pos = max_element(dp.begin(), dp.end()) - dp.begin() ;
    cout << dp[pos] << "\n" ;
    vector<int> res ;
    while (pos != -1) {
        res.push_back(pos) ;
        pos = pr[pos] ;
    }
    reverse(res.begin(), res.end()) ;
    for (int i : res) cout << i + 1 << ' ' ;
    return 0 ;
}

Compilation message (stderr)

subsequence.cpp: In function 'int32_t main()':
subsequence.cpp:9:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     int n ; scanf("%d", &n) ;
      |             ~~~~~^~~~~~~~~~
subsequence.cpp:11:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     for (int &i : a) scanf("%d", &i) ;
      |                      ~~~~~^~~~~~~~~~
subsequence.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     for (int &i : k) scanf("%d", &i) ;
      |                      ~~~~~^~~~~~~~~~

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