Submission #895729

#	Time	Username	Problem	Language	Result	Execution time	Memory
895729		Neco_arc	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4950 ms	89388 KiB

subsequence

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define VietAnh "Longest beautiful sequence"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 1e5 + 7

using namespace std;

const ll mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n;
int dp[maxn], a[maxn];
int L[(1 << 10) + 1][(1 << 10) + 1][21];
int p[maxn];

void Trace_Back(int id)
{
    vector<int> ans = {id};
    int pre = id;
    fid(i, id - 1, 1)
    {
        if(cntbit(a[i] & a[pre]) == p[pre] && (dp[i] == dp[pre] - 1)){
            ans.push_back(i);
            pre = i;
        }
    }

    reverse(all(ans));
    for(int x : ans) cout << x << " ";
}

void sub1()
{
    int ans = 0;
    fi(i, 1, n)
    {
        dp[i] = 1;
        fid(j, i - 1, 1) {
            if(cntbit(a[i] & a[j]) == p[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        ans = max(ans, dp[i]);
    }

    cout << ans << '\n';

    fi(i, 1, n) if(dp[i] == ans) {
        Trace_Back(i);
        return;
    }

}

tuple<int, int> dcm(int x)
{
    int l = 0, r = 0;
    fi(i, 1, 10) if(getbit(x, i - 1)) l |= (1 << (i - 1));
    fi(i, 11, 20) if(getbit(x, i - 1)) r |= (1 << (i - 10 - 1));
    return {l, r};
}

void sub2()
{
    int ans = 0;
    fi(i, 1, n)
    {
        dp[i] = 1;
        int Left, Right;
        tie(Left, Right) = dcm(a[i]);

        fi(l, 0, (1 << 10) - 1) dp[i] = max(dp[i], L[l][Right][p[i] - cntbit(l & Left)] + 1);
        fi(r, 0, (1 << 10) - 1) L[Left][r][cntbit(r & Right)] = max(L[Left][r][cntbit(r & Right)], dp[i]);

        ans = max(ans, dp[i]);
    }
//    cout << '\n';
//
    cout << ans << '\n';

    fi(i, 1, n) if(dp[i] == ans) {
        Trace_Back(i);
        return;
    }

}

void solve()
{

    cin >> n;
//
    fi(i, 1, n) cin >> a[i];
    fi(i, 1, n) cin >> p[i];

    sub2();


}


int main()
{

    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(VietAnh".inp", "r")) {
        freopen(VietAnh".inp", "r", stdin);
        freopen(VietAnh".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;

    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'std::tuple<int, int> dcm(int)':
subsequence.cpp:72:33: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   72 |     fi(i, 1, 10) if(getbit(x, i - 1)) l |= (1 << (i - 1));
      |                               ~~^~~
subsequence.cpp:8:28: note: in definition of macro 'getbit'
    8 | #define getbit(x,i) ((x >> i)&1)
      |                            ^
subsequence.cpp:73:34: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   73 |     fi(i, 11, 20) if(getbit(x, i - 1)) r |= (1 << (i - 10 - 1));
      |                                ~~^~~
subsequence.cpp:8:28: note: in definition of macro 'getbit'
    8 | #define getbit(x,i) ((x >> i)&1)
      |                            ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(VietAnh".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(VietAnh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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