제출 #1013622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013622		_fractal	Kpart (eJOI21_kpart)	C++14	30 / 100	2019 ms	11600 KiB

Main

#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();
    
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70