oj.uz

Submission #890062

# Submission time Handle Problem Language Result Execution time Memory
890062 2023-12-20T13:33:52 Z sleepntsheep Kpart (eJOI21_kpart) C++17
0 / 100
 2000 ms 476 KB 
#include <iostream>
#include <bitset>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <numeric>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using namespace std;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);

void docase()
{
    int n;
    cin >> n;
    vector<int> a(n);
    vector<long long> b;
    for (auto &x : a) cin >> x;

    inclusive_scan(ALL(a), back_inserter(b), plus<long long>(), 0ll);

    auto ok = [&](int k){
        bitset<100001> ss = 1;

        for (int i = 0; i < n; ++i)
        {
            if (i + 1 >= k) ss = ss & (ss >> a[i-k+1]);
            ss = ss | (ss << a[i]);
            if (i - k + 1 >= 0)
            {
                auto sum = b[i] - (i - k >= 0 ? b[i-k] : 0);
                //cout << i << ' ' << sum << '\n';
                if ((sum & 1) || !ss[sum >> 1]) return 0;
            }
        }

        vector<vector<int>> t(2*n);

        /*
        auto ins = [&](auto &&ins, int v, int l, int r, int x, int y, int k){
            if (r < x || y < l) return;
            if (x <= l && r <= y) { t[v].push_back(k); return; }
            auto m = midpoint(l, r), vl = v+ 1, vr = v + (m-l+1)*2;
            ins(ins, vl, l, m, x, y, k);
            ins(ins, vr, m+1, r, x, y, k);
        };

        for (int i = 0; i < n; ++i) ins(ins, 0, 0, n-1, i, i+k-1, i);

        for 
        */

        return 1;
    };

    vector<int> ans;
    for (int l = 1; l <= n; ++l) if (ok(l)) ans.push_back(l);
    cout << ans.size() << ' '; for (auto &x : ans) cout << x << ' ';
    cout << '\n';
}

int main()
{
    ShinLena;
    int T;
    cin >> T;
    while (T--) docase();
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

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