Submission #226046

#	Time	Username	Problem	Language	Result	Execution time	Memory
226046		emil_physmath	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	476 ms	262144 KiB

subsequence

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <set>
using namespace std;
#define Bits __builtin_popcount
using uint = unsigned int;
const int maxN = 100'000;
struct DP
{
    int ind, len, prev;
    DP(int ind_ = -1, int len_ = 0, int prev_ = -1)
        : ind(ind_)
        , len(len_)
        , prev(prev_)
    {}
    operator int&() { return len; }
    operator const int&() const { return len; }
};
inline void Upd(DP& a, const DP& rhs)
{
    if (rhs.len + 1 >= a.len)
    {
        a.len = rhs.len + 1;
        a.prev = rhs.ind;
    }
}
 
DP best[1 << 10][1 << 10][21];
DP dp[maxN];
int a[maxN], k[maxN];
 
int main()
{
    FILE * in;
    in = fopen("subsequence.in", "r");
    int n;
    // cin >> n;
    fscanf(in, "%d", &n);
    for (int i = 0; i < n; ++i)
        fscanf(in, "%d", &a[i]);
        // cin >> a[i];
    for (int i = 0; i < n; ++i)
        fscanf(in, "%d", &k[i]);
        // cin >> k[i];
    for (int i = 0; i < n; ++i)
    {
        dp[i].ind = i;
        if (i == 0)
            dp[i].len = 1, dp[i].prev = -1;
        else
            for (uint lmask = 0; lmask < (1 << 10); ++lmask)
            {
                int lk = Bits(a[i] & (lmask << 10));
                if (lk > k[i]) continue;
                uint rpart = (1 << 10) - 1;
                rpart &= a[i];
                Upd(dp[i], best[lmask][rpart][k[i] - lk]);
            }
        uint lpart = (1 << 10) - 1;
        lpart <<= 10;
        lpart &= a[i];
        lpart >>= 10;
        for (uint mask = 0; mask < (1 << 10); ++mask)
        {
            DP& bst = best[lpart][mask][Bits(a[i] & mask)];
            if (bst.len <= dp[i].len)
                bst = dp[i];
        }
#ifdef MANSON
        cerr << "dp[" << dp[i].ind << "] = " << dp[i].len << ", prev: " << dp[i].prev << '\n';
#endif
    }
    FILE * out;
    out = fopen("subsequence.out", "w");
    vector<int> ans;
    for (int i = max_element(dp, dp + n) - dp; i != -1; i = dp[i].prev)
        ans.push_back(i);
    fprintf(out, "%d\n", (int)ans.size());
    reverse(ans.begin(), ans.end());
    for (int i: ans)
        fprintf(out, "%d ", i + 1);
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:42:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(in, "%d", &n);
     ~~~~~~^~~~~~~~~~~~~~
subsequence.cpp:44:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(in, "%d", &a[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~
subsequence.cpp:47:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(in, "%d", &k[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~

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