Submission #472429

#	Time	Username	Problem	Language	Result	Execution time	Memory
472429		Shin	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	3 ms	4428 KiB

subsequence

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK "task"
#define all(x) x.begin(), x.end()
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

typedef long long ll;
typedef unsigned long long ull;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

#define right __right
#define left __left

int get_right(int mask) {
    return mask & (MASK(10) - 1);
}
int get_left(int mask) {
    return mask & ((MASK(20) - 1) ^ (MASK(10) - 1));
}

int cnt_bit(int mask) {
    return __builtin_popcount(mask);
}

int n;
int a[N];
int k[N];
int best[N];
int trace[N];
int dp[MASK(10)][MASK(10)][11];
    
void solve(void) { 
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &a + i);
    for (int i = 1; i <= n; i ++) scanf("%d", &k + i);
    

    for (int i = 1; i <= n; i ++) {
        int left = get_left(a[i]);
        int right = get_right(a[i]);

        for (int mask = 0; mask < MASK(10); mask ++) {
            int need = k[i] - cnt_bit(right & mask);
            if (0 > need || need > 10) continue;
            if (maximize(best[i], best[dp[left][mask][need]] + 1)) {
                trace[i] = dp[left][mask][need];
            }
        }

        for (int mask = 0; mask < MASK(10); mask ++) {
            int cntbit = cnt_bit(mask & left);
            if (best[i] > best[dp[mask][right][cntbit]])
                dp[mask][right][cntbit] = i;
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++) if (best[i] > best[res])
        res = i;

    vector<int> idx;
    for (int i = res; i; i = trace[i]) idx.push_back(i);
    printf("%d\n", idx.size());
    reverse(all(idx));
    for (int i: idx) printf("%d ", i);    
}

int main(void) {
    int test = 1;
    // cin >> test;
    while (test --) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'void solve()':
subsequence.cpp:50:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int (*)[200007]' [-Wformat=]
   50 |     for (int i = 1; i <= n; i ++) scanf("%d", &a + i);
      |                                          ~^   ~~~~~~
      |                                           |      |
      |                                           int*   int (*)[200007]
subsequence.cpp:51:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int (*)[200007]' [-Wformat=]
   51 |     for (int i = 1; i <= n; i ++) scanf("%d", &k + i);
      |                                          ~^   ~~~~~~
      |                                           |      |
      |                                           int*   int (*)[200007]
subsequence.cpp:79:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   79 |     printf("%d\n", idx.size());
      |             ~^     ~~~~~~~~~~
      |              |             |
      |              int           std::vector<int>::size_type {aka long unsigned int}
      |             %ld
subsequence.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
subsequence.cpp:50:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     for (int i = 1; i <= n; i ++) scanf("%d", &a + i);
      |                                   ~~~~~^~~~~~~~~~~~~~
subsequence.cpp:51:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     for (int i = 1; i <= n; i ++) scanf("%d", &k + i);
      |                                   ~~~~~^~~~~~~~~~~~~~

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