Submission #536220

#TimeUsernameProblemLanguageResultExecution timeMemory
536220akhan42Bootfall (IZhO17_bootfall)C++17
100 / 100
598 ms4188 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define F first #define S second #define forn(i, n) for(int i = 0; i < n; ++i) #define forbn(i, b, n) for(int i = b; i < n; ++i) #define sz(v) (int)v.size() #define pb push_back #define mp make_pair #define eb emplace_back #define all(v) v.begin(), v.end() #define min3(a, b, c) min(a, min(b, c)) #define lc v << 1 #define rc (v << 1) + 1 typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef long long ll; typedef complex<double> cd; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; template <class T> inline void mineq(T &a, T b) { a = min(a, b); } template <class T> inline void maxeq(T &a, T b) { a = max(a, b); } int mod = 1000 * 1000 * 1000 + 7; int total = 0; vi pol2; int add(int a, int b) { int res = (a + b) % mod; return res < 0 ? res + mod : res; } int ct[250001]; vii changes; void divide(int d, int sh) { changes.clear(); for(int i = total; i - d >= 0 && i - d + sh >= total / 2; i--) { if(pol2[i] != 0) { changes.eb(i - d, pol2[i - d]); pol2[i - d] = add(pol2[i - d], -pol2[i]); ct[i - d + sh] += 1; } } for(ii p: changes) pol2[p.F] = p.S; } void solve() { int n; cin >> n; vi arr(n); set<int> nums; forn(i, n) { cin >> arr[i]; nums.insert(arr[i]); } sort(all(arr)); bool odd = true, even = true; for(int a: arr) { total += a; if(a % 2) even = false; else odd = false; } pol2.assign(total + 1, 0); pol2[0] = 1; for(int a: arr) { for(int i = total - a; i >= 0; i--) { pol2[i + a] = add(pol2[i + a], pol2[i]); } } if(total % 2 || pol2[total / 2] == 0 || (!even && !odd)) { cout << 0; return; } int tt = sz(nums); for(int a: nums) { int d = (a + (odd ? 1 : 0)) / 2; divide(a, d); } vi vans; int rem = (odd ? 1 : 0) + total; forbn(i, (rem + 1) / 2, total + 1) { if(ct[i] == tt) { vans.pb(2 * i - rem); } } cout << sz(vans) << '\n'; for(int el: vans) cout << el << ' '; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // freopen("triangles.in", "r", stdin); // freopen("triangles.out", "w", stdout); int t = 1; // cin >> t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...