제출 #536144

#제출 시각아이디문제언어결과실행 시간메모리
536144akhan42Bootfall (IZhO17_bootfall)C++17
13 / 100
5 ms1112 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #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); } const double PI = acos(-1); void fft(vector<cd> & a, bool invert) { int n = a.size(); for (int i = 1, j = 0; i < n; i++) { int bit = n >> 1; for (; j & bit; bit >>= 1) j ^= bit; j ^= bit; if (i < j) swap(a[i], a[j]); } for (int len = 2; len <= n; len <<= 1) { double ang = 2 * PI / len * (invert ? -1 : 1); cd wlen(cos(ang), sin(ang)); for (int i = 0; i < n; i += len) { cd w(1, 0); for (int j = 0; j < len / 2; j++) { cd u = a[i+j], v = a[i+j+len/2] * w; a[i+j] = u + v; a[i+j+len/2] = u - v; w *= wlen; } } } if (invert) { for (cd & x : a) x /= n; } } vector<int> multiply(vector<int> const& a, vector<int> const& b) { vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end()); int n = 1; while (n < sz(a) + sz(b)) n <<= 1; fa.resize(n); fb.resize(n); fft(fa, false); fft(fb, false); for (int i = 0; i < n; i++) fa[i] *= fb[i]; fft(fa, true); vector<int> result(n); for (int i = 0; i < n; i++) result[i] = round(fa[i].real()); return result; } const int BASE = 350; const int MX = BASE * BASE + 1; using bts = bitset<MX>; int last_bit(bts& a) { int i = a._Find_first(); while(a._Find_next(i) != a.size()) i = a._Find_next(i); return i; } bts sum(bts& a, bts& b) { int al = last_bit(a), bl = last_bit(b); vi v1, v2; forn(i, al + 1) v1.pb(a[i]); forn(i, bl + 1) v2.pb(b[i]); vi c = multiply(v1, v2); bts res; forn(i, min(sz(c), MX)) if(c[i] > 0) res[i] = 1; return res; } vi pols[500]; vi mult(int l, int r) { if(l == r) return pols[l]; int m = (l + r) / 2; vi r1 = mult(l, m); vi r2 = mult(m + 1, r); return multiply(r1, r2); } bts divide(vi pol, int d) { bts res; int ln = min(sz(pol), MX); for(int i = 0; i < ln; i++) { if(pol[i] > 0) { pol[i + d] -= pol[i]; pol[i] = 0; res[i] = 1; } } return res; } void solve() { int n; cin >> n; vi arr(n); forn(i, n) cin >> arr[i]; sort(all(arr)); forn(i, n) { pols[i].resize(arr[i] + 1); pols[i][0] = pols[i][arr[i]] = 1; } bts s; s[0] = 1; int total = 0; bool odd = true, even = true; for(int a: arr) { s |= s << a; total += a; if(a % 2) even = false; else odd = false; } if(total % 2 || s[total / 2] == 0 || (!even && !odd)) { cout << 0; return; } vi pol = mult(0, n - 1); bts ans; ans.flip(); forn(i, n) { bts c = divide(pol, arr[i]); int d = (total - arr[i] - (odd ? 1 : 0)) / 2; ans &= c >> d; } vi vans; forbn(i, 1, MX) { if(ans[i]) { vans.pb(2 * i - (odd ? 1 : 0)); } } 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...