oj.uz

Submission #1013622

# Submission time Handle Problem Language Result Execution time Memory
1013622 2024-07-03T17:39:34 Z _fractal Kpart (eJOI21_kpart) C++14
30 / 100
 2000 ms 11600 KB 
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define make_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = 1e3 + 20;
const int M = 1e6;
const int inf = 2e9 + 3;
const ll INF = 1e18;

const int S = 100000;
bitset<2 * S + 1> B[N];
int good[N][N], is[N], a[N];

void rec(int l, int r) {
    if (l == r) {
        if (a[l] == 0) good[l][l] = 1;
        return;
    }
    int m = l + r >> 1;
    B[m + 1].reset();
    B[m + 1][S + a[m + 1]] = 1;
    B[m + 1][S - a[m + 1]] = 1;
    for (int i = m + 2; i <= r; ++i) {
        B[i] = (B[i - 1] << a[i]) | (B[i - 1] >> a[i]);
    }
    B[m].reset();
    B[m][S + a[m]] = 1;
    B[m][S - a[m]] = 1;
    for (int i = m; i >= l; --i) {
        if (i < m) B[i] = (B[i + 1] << a[i]) | (B[i + 1] >> a[i]);
        for (int j = m + 1; j <= r; ++j) {
            if ((B[j] & B[i]).count() > 0) {
                good[i][j] = 1;
            }
        }
    }
    rec(l, m);
    rec(m + 1, r);
}

int n;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        for (int j = i; j <= n; ++j) good[i][j] = 0;
        is[i] = 1;
    }
    rec(1, n);
    int ans = n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            if (!good[j][i]) {
                if (is[i - j + 1] == 1)
                    ans--;
                is[i - j + 1] = 0;
            }
        }
    }
    cout << ans << '\n';
    for (int i = 1; i <= n; ++i) {
        if (is[i]) cout << i << " ";
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    
}

Compilation message

Main.cpp: In function 'void rec(int, int)':
Main.cpp:31:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int m = l + r >> 1;
      |             ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4952 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 7372 KB Output is correct
2 Correct 1144 ms 9424 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2019 ms 11600 KB Time limit exceeded
2 Halted 0 ms 0 KB -