# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
855104 | 2023-09-30T07:17:43 Z | Alfraganus | Bootfall (IZhO17_bootfall) | C++17 | 349 ms | 262144 KB |
#include <bits/stdc++.h> using namespace std; #define fs first #define ss second #define endl '\n' #define all(a) a.begin(), a.end() #define print(a) \ for(auto x : a) \ cout << x << ' '; \ cout << endl; #define printmp(a) \ for (auto x : a) \ cout << x.fs << ' ' << x.ss << endl; vector<vector<bool>> dp; void solve(){ int n; cin >> n; vector<int> a(n); int sum = 0; bool even = false, odd = false; for(int i = 0; i < n; i ++) cin >> a[i], sum += a[i], even |= !(a[i] & 1), odd |= (a[i] & 1); sort(all(a)); if((sum & 1)){ cout << 0; return; } if(even and odd){ cout << 0; return; } queue<int> q; q.push(sum / 2); bool flag = false; while(!q.empty()){ int x = q.front(); q.pop(); if(x == 0) flag = 1; if(!flag){ for(int i = 0; i < n; i ++){ if(x >= a[i]){ q.push(x - a[i]); } } } } if(!flag){ cout << 0; return; } dp.resize(n, vector<bool> (sum)); for(int i = 0; i < n; i ++){ dp[i][0] = 1; vector<int> b; for(int j = 0; j < n; j ++){ if(i != j){ dp[i][a[j]] = 1; for (auto x : b) { if (x + a[j] < (int)dp[0].size() and dp[i][x + a[j]] == 0) { dp[i][x + a[j]] = 1; b.push_back(x + a[j]); } } b.push_back(a[j]); } } b.clear(); } if(even){ vector<int> ans; for(int j = 2; j <= sum - a[0]; j += 2){ int c = sum; for(int i = 0; i < n; i ++){ sum -= a[i]; sum += j; if(!((sum / 2 < dp[0].size() and sum / 2 >= 0 and dp[i][sum / 2]) or (sum / 2 - j < dp[0].size() and sum / 2 >= j and dp[i][sum / 2 - j]))) break; sum -= j; sum += a[i]; if(i == n - 1) ans.push_back(j); } sum = c; } cout << ans.size() << endl; print(ans) } else{ vector<int> ans; for (int j = 1; j <= sum - a[0]; j += 2) { int c = sum; for (int i = 0; i < n; i++) { sum -= a[i]; sum += j; if (!((sum / 2 < dp[0].size() and sum / 2 >= 0 and dp[i][sum / 2]) or (sum / 2 - j < dp[0].size() and sum / 2 >= j and dp[i][sum / 2 - j]))) break; sum -= j; sum += a[i]; if (i == n - 1) ans.push_back(j); } sum = c; } cout << ans.size() << endl; print(ans) } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while(t --){ solve(); cout << endl; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 2 ms | 1372 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 14 ms | 6932 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 2 ms | 1372 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 14 ms | 6932 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Runtime error | 349 ms | 262144 KB | Execution killed with signal 9 |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 2 ms | 1372 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 14 ms | 6932 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Runtime error | 349 ms | 262144 KB | Execution killed with signal 9 |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 2 ms | 1372 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 14 ms | 6932 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Runtime error | 349 ms | 262144 KB | Execution killed with signal 9 |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 2 ms | 1372 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 14 ms | 6932 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Runtime error | 349 ms | 262144 KB | Execution killed with signal 9 |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 2 ms | 1372 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 14 ms | 6932 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Runtime error | 349 ms | 262144 KB | Execution killed with signal 9 |
11 | Halted | 0 ms | 0 KB | - |