| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 36063 | 2017-12-05T04:20:43 Z | UncleGrandpa925 | Bootfall (IZhO17_bootfall) | C++14 | 6 ms | 4128 KB |
/*input
4
1 3 1 5
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define N 505
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
for (int i = 0; i < x.size(); i++) os << x[i] << sp;
return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
cout << x.fi << sp << x.se << sp;
return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
for (int i = 0; i < x.size(); i++) os << x[i] << endl;
return os;
}
const int mod = 1e9 + 7;
int n;
int a[N];
int f[250005];
int sum = 0;
int mark[250005];
vector<int> order;
void add(int x) {
for (int i = sum; i >= 0; i--) {
f[i + x] += f[i];
if (f[i + x] >= mod) f[i + x] -= mod;
}
sum += x;
}
void sub(int x) {
for (int i = 0; i <= sum; i++) {
f[i + x] += (mod - f[i]);
if (f[i + x] >= mod) f[i + x] -= mod;
}
sum -= x;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
f[0] = 1;
for (int i = 1; i <= n; i++) cin >> a[i], add(a[i]);
if (sum % 2 || f[sum / 2] == 0) {
cout << 0 << endl;
return 0;
}
for (int i = 1; i <= n; i++) {
sub(a[i]);
int sta = 1; if (sum % 2 == 0) sta++;
for (int j = sta; j <= sum; j += 2) {
if (f[(sum + j) / 2 - j])
mark[j]++;
}
add(a[i]);
}
for (int i = 1; i <= sum; i++) if (mark[i] == n) order.push_back(i);
cout << order.size() << endl;
cout << order << endl;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 4128 KB | Output is correct |
| 2 | Correct | 0 ms | 4128 KB | Output is correct |
| 3 | Correct | 0 ms | 4128 KB | Output is correct |
| 4 | Correct | 0 ms | 4128 KB | Output is correct |
| 5 | Correct | 0 ms | 4128 KB | Output is correct |
| 6 | Correct | 0 ms | 4128 KB | Output is correct |
| 7 | Correct | 0 ms | 4128 KB | Output is correct |
| 8 | Correct | 0 ms | 4128 KB | Output is correct |
| 9 | Correct | 0 ms | 4128 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 4128 KB | Output is correct |
| 2 | Correct | 0 ms | 4128 KB | Output is correct |
| 3 | Correct | 0 ms | 4128 KB | Output is correct |
| 4 | Correct | 0 ms | 4128 KB | Output is correct |
| 5 | Correct | 0 ms | 4128 KB | Output is correct |
| 6 | Correct | 0 ms | 4128 KB | Output is correct |
| 7 | Correct | 0 ms | 4128 KB | Output is correct |
| 8 | Correct | 0 ms | 4128 KB | Output is correct |
| 9 | Correct | 0 ms | 4128 KB | Output is correct |
| 10 | Correct | 0 ms | 4128 KB | Output is correct |
| 11 | Correct | 0 ms | 4128 KB | Output is correct |
| 12 | Correct | 0 ms | 4128 KB | Output is correct |
| 13 | Correct | 0 ms | 4128 KB | Output is correct |
| 14 | Correct | 0 ms | 4128 KB | Output is correct |
| 15 | Correct | 0 ms | 4128 KB | Output is correct |
| 16 | Correct | 0 ms | 4128 KB | Output is correct |
| 17 | Correct | 0 ms | 4128 KB | Output is correct |
| 18 | Correct | 0 ms | 4128 KB | Output is correct |
| 19 | Correct | 0 ms | 4128 KB | Output is correct |
| 20 | Correct | 0 ms | 4128 KB | Output is correct |