Submission #299673

#	Time	Username	Problem	Language	Result	Execution time	Memory
299673		BeanZ	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	5 ms	5120 KiB

subsequence

// I_LOVE_LPL
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
ll a[N], k[N], dp[N], par[N][50];
set<ll, greater<ll>> s[N];
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("A.inp", "r")){
                freopen("test.inp", "r", stdin);
                freopen("test.ans", "w", stdout);
        }
        ll n;
        cin >> n;
        ll ans = 0;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> k[i], s[k[i]].insert(i);
        for (int i = 1; i <= n; i++) dp[i] = 1;
        for (int i = 1; i <= n; i++){
                for (int j = 1; j < i; j++){
                        ll x = a[i] & a[j];
                        auto it = s[__builtin_popcount(x)].lower_bound(dp[j] + 1);
                        if (it != s[__builtin_popcount(x)].end()){
                                dp[i] = max(dp[i], (*it));
                                par[i][(*it)] = j;
                        }
                }
                ans = max(ans, dp[i]);
        }
        cout << ans << endl;
        ll cur;
        for (int i = 1; i <= n; i++) if (dp[i] == ans) cur = i;
        vector<ll> mem;
        mem.push_back(cur);
        while (ans > 1){
                cur = par[cur][ans];
                mem.push_back(cur);
                ans--;
        }
        reverse(mem.begin(), mem.end());
        for (auto j : mem) cout << j << " ";
}
/*
5
5 3 5 3 5
10 1 20 1 20

4
1 2 3 4
10 0 1 0

2
8 9
20 0
*/

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:15:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   15 |                 freopen("test.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   16 |                 freopen("test.ans", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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