답안 #950119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
950119	2024-03-20T05:33:13 Z	Pragmatism	Bootfall (IZhO17_bootfall)	C++17	13 / 100	347 ms	600 KB

bootfall

//Bismillahir-Rahmanir-Rahim

#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,popcnt,avx,avx2")

#define pb push_back
#define pii pair <int, int>
#define pll pair <long long, long long>
#define pld pair <long double, long double>
#define ll long long
#define ld long double
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define skip continue
#define bpop(x) (ll)__builtin_popcountll(x)

using namespace std;

const int N = 5e2 + 7;
const int W = 1e4 + 7;
const int maxA = 1e5 + 7;
const int inf = 1e9 + 7;
const ll INF = 2e18 + 7;
const int MOD = 998244353;
const ld eps = 1e-9;

pii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//clock_t start = clock();

#define int short

int n, a[N], dp[W];
void add(int x) {
    for (int w = W - 1;w >= 0;w--) {
        if (w + x < W)dp[w + x] += dp[w];
    }
    dp[x]++;
}
void del(int x) {
    dp[x]--;
    for (int w = x;w < W;w++)dp[w] -= dp[w - x];
}
bool check(int Tima) {
    for (int w = 0;w < W;w++)dp[w] = 0;
    int sum = 0;
    for (int i = 1;i <= n;i++)add(a[i]), sum += a[i];
    if (sum % 2 == 1 || !dp[sum / 2])return 0;
    add(Tima), sum += Tima;
    for (int i = 1;i <= n;i++) {
        sum -= a[i], del(a[i]);
        if (sum % 2 == 1 || !dp[sum / 2])return 0;
        sum += a[i], add(a[i]);
    }
    return 1;
}
void solve() {
    cin >> n;
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++) {
        if (a[i] % 2 != a[1] % 2)cout << 0, exit(0);
    }
    int chet = a[1] % 2;
    vector <int> ans;
    for (int Tima = chet;Tima <= 1000;Tima += 2) {
        if (check(Tima))ans.pb(Tima);
    }
    cout << sz(ans) << '\n';
    for (auto Tima : ans)cout << Tima << ' ';
}
signed main() {
    //srand(time(NULL));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("subsequence.in", "r", stdin);
    //freopen("subsequence.out", "w", stdout);
    int test = 1;
    //cin >> test;
    for (int t = 1;t <= test;t++) {
        //cout << "Case " << t << ": ";
        solve();
    }
    return 0;
}

Compilation message

bootfall.cpp:4: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    4 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	348 KB	Output is correct
2	Correct	18 ms	348 KB	Output is correct
3	Correct	6 ms	344 KB	Output is correct
4	Correct	13 ms	472 KB	Output is correct
5	Correct	40 ms	344 KB	Output is correct
6	Correct	20 ms	344 KB	Output is correct
7	Correct	15 ms	348 KB	Output is correct
8	Correct	47 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	348 KB	Output is correct
2	Correct	18 ms	348 KB	Output is correct
3	Correct	6 ms	344 KB	Output is correct
4	Correct	13 ms	472 KB	Output is correct
5	Correct	40 ms	344 KB	Output is correct
6	Correct	20 ms	344 KB	Output is correct
7	Correct	15 ms	348 KB	Output is correct
8	Correct	47 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	66 ms	348 KB	Output is correct
11	Correct	106 ms	448 KB	Output is correct
12	Correct	64 ms	448 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	91 ms	344 KB	Output is correct
15	Correct	94 ms	344 KB	Output is correct
16	Correct	103 ms	448 KB	Output is correct
17	Correct	54 ms	348 KB	Output is correct
18	Correct	75 ms	448 KB	Output is correct
19	Correct	75 ms	348 KB	Output is correct
20	Correct	68 ms	348 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	348 KB	Output is correct
2	Correct	18 ms	348 KB	Output is correct
3	Correct	6 ms	344 KB	Output is correct
4	Correct	13 ms	472 KB	Output is correct
5	Correct	40 ms	344 KB	Output is correct
6	Correct	20 ms	344 KB	Output is correct
7	Correct	15 ms	348 KB	Output is correct
8	Correct	47 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	66 ms	348 KB	Output is correct
11	Correct	106 ms	448 KB	Output is correct
12	Correct	64 ms	448 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	91 ms	344 KB	Output is correct
15	Correct	94 ms	344 KB	Output is correct
16	Correct	103 ms	448 KB	Output is correct
17	Correct	54 ms	348 KB	Output is correct
18	Correct	75 ms	448 KB	Output is correct
19	Correct	75 ms	348 KB	Output is correct
20	Correct	68 ms	348 KB	Output is correct
21	Incorrect	347 ms	600 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	348 KB	Output is correct
2	Correct	18 ms	348 KB	Output is correct
3	Correct	6 ms	344 KB	Output is correct
4	Correct	13 ms	472 KB	Output is correct
5	Correct	40 ms	344 KB	Output is correct
6	Correct	20 ms	344 KB	Output is correct
7	Correct	15 ms	348 KB	Output is correct
8	Correct	47 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	66 ms	348 KB	Output is correct
11	Correct	106 ms	448 KB	Output is correct
12	Correct	64 ms	448 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	91 ms	344 KB	Output is correct
15	Correct	94 ms	344 KB	Output is correct
16	Correct	103 ms	448 KB	Output is correct
17	Correct	54 ms	348 KB	Output is correct
18	Correct	75 ms	448 KB	Output is correct
19	Correct	75 ms	348 KB	Output is correct
20	Correct	68 ms	348 KB	Output is correct
21	Incorrect	347 ms	600 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	348 KB	Output is correct
2	Correct	18 ms	348 KB	Output is correct
3	Correct	6 ms	344 KB	Output is correct
4	Correct	13 ms	472 KB	Output is correct
5	Correct	40 ms	344 KB	Output is correct
6	Correct	20 ms	344 KB	Output is correct
7	Correct	15 ms	348 KB	Output is correct
8	Correct	47 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	66 ms	348 KB	Output is correct
11	Correct	106 ms	448 KB	Output is correct
12	Correct	64 ms	448 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	91 ms	344 KB	Output is correct
15	Correct	94 ms	344 KB	Output is correct
16	Correct	103 ms	448 KB	Output is correct
17	Correct	54 ms	348 KB	Output is correct
18	Correct	75 ms	448 KB	Output is correct
19	Correct	75 ms	348 KB	Output is correct
20	Correct	68 ms	348 KB	Output is correct
21	Incorrect	347 ms	600 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	348 KB	Output is correct
2	Correct	18 ms	348 KB	Output is correct
3	Correct	6 ms	344 KB	Output is correct
4	Correct	13 ms	472 KB	Output is correct
5	Correct	40 ms	344 KB	Output is correct
6	Correct	20 ms	344 KB	Output is correct
7	Correct	15 ms	348 KB	Output is correct
8	Correct	47 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	66 ms	348 KB	Output is correct
11	Correct	106 ms	448 KB	Output is correct
12	Correct	64 ms	448 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	91 ms	344 KB	Output is correct
15	Correct	94 ms	344 KB	Output is correct
16	Correct	103 ms	448 KB	Output is correct
17	Correct	54 ms	348 KB	Output is correct
18	Correct	75 ms	448 KB	Output is correct
19	Correct	75 ms	348 KB	Output is correct
20	Correct	68 ms	348 KB	Output is correct
21	Incorrect	347 ms	600 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

답안 #950119

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 15.0

Subtask #4 0 / 16.0

Subtask #5 0 / 21.0

Subtask #6 0 / 35.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 15.0

Subtask #4
0 / 16.0

Subtask #5
0 / 21.0

Subtask #6
0 / 35.0