Submission #699804

#	Time	Username	Problem	Language	Result	Execution time	Memory
699804		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3753 ms	48340 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int, int> ii;

void print() {cerr << '\n';} template<typename t1, typename... t2>
void print(t1 a, t2... b) {cerr << a << ' ', print(b...);}
const int N = 1e5 + 5;
int n, a[N];
int k[N];

#define countBit(a) (__builtin_popcount(a))
namespace sub2
{
ii dp[N];
void solve()
{
    int mx = 0;
    for(int i = 1; i <= n; i++) dp[i] = {1, 0};
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j < i; j++)
            if(countBit(a[i] & a[j]) == k[i])
                dp[i] = max(dp[i], {dp[j].F + 1, j});
        mx = max(mx, dp[i].F);
    }

    cout << mx << '\n';
    vector<int> res;
    for(int i = 1; i <= n; i++)
        if(dp[i].F == mx)
        {
            do
            {
                res.pb(i);
                i = dp[i].S;
            }while(i != 0);
            break;
        }
    reverse(all(res));
    for(int &x : res) cout << x << ' ';
}
};

namespace sub4
{
ii dp[N + 5];
int f[1 << 10][1 << 10][11]{};
void solve()
{
    int mx = 0;
    for(int i = 1; i <= n; i++)
    {
        int L = a[i] >> 10;
        int R = a[i] ^ (L << 10);
        dp[i] = {1, 0};
        for(int curL = 0; curL < (1 << 10); curL++)
        {
            int cntR = k[i] - countBit(L & curL);
            int j = f[curL][R][cntR];
            if(cntR < 0 || cntR > 10 || j == 0) continue;
            dp[i] = max(dp[i], {dp[j].F + 1, j});
        }
        mx = max(mx, dp[i].F);
        for(int nxtR = 0; nxtR < (1 << 10); nxtR++)
        {
            int cntR = countBit(R & nxtR);
            int &j = f[L][nxtR][cntR];
            if(j == 0 || dp[j].F < dp[i].F) j = i;
        }
    }
    cout << mx << '\n';
    vector<int> res;
    for(int i = 1; i <= n; i++)
        if(dp[i].F == mx)
        {
            do
            {
                res.pb(i);
                i = dp[i].S;
            }while(i != 0);
            break;
        }
    reverse(all(res));
    for(int &x : res) cout << x << ' ';
}
};

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
        cin >> k[i];
    if(n <= 5000)
        sub2::solve();
    else
        sub4::solve();
}

signed main()
{
    if(fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

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

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