Submission #1215208

#TimeUsernameProblemLanguageResultExecution timeMemory
1215208M_SH_OBootfall (IZhO17_bootfall)C++20
65 / 100
1095 ms1140 KiB
#include <bits/stdc++.h> //#include "grader.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll int #define ll1 long long #define ull unsigned long long #define dou long double #define str string #define vll vector<ll> #define vi vector<int> #define pll pair<ll, ll> #define vpll vector<pll> #define vbool vector<bool> #define vstr vector<str> #define vvll vector<vll> #define pb push_back #define pf push_front #define endl "\n" #define fr first #define se second // #define sortcmp(a) sort(a.begin(), a.end(), cmp) #define sort(a) sort(a.begin(), a.end()) #define all(a) a.begin(), a.end() #define reverse(a) reverse(a.begin(), a.end()) #define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define INF 5000000000000000000 #define ordered_set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> using namespace std; using namespace __gnu_pbds; mt19937 rng(1488); ll randll(ll l, ll r){ return uniform_int_distribution<ll>(l, r)(rng); } /*vector<map<ll, vll>> s; vll p; ll find(ll v) { if (p[v] == v) return v; return p[v] = find(p[v]); } void unite(ll a, ll b) { a = find(a); b = find(b); if (a == b) return; if (s[a].size() < s[b].size()) { p[a] = b; for (auto i : s[a]) { for (int j : i.se) { s[b][i.fr].pb(j); } } s[a].clear(); } else { p[b] = a; for (auto i : s[b]) { for (int j : i.se) { s[a][i.fr].pb(j); } } s[b].clear(); } } vll tree1; void bt(ll v, ll tl, ll tr, vll& a) { if (tl == tr) { tree1[v] = a[tl]; return; } ll tm = (tl+tr)/2; bt(v*2, tl, tm, a); bt(v*2, tm+1, tr, a); tree1[v] = tree1[v*2]+tree1[v*2+1]; } ll get(ll l, ll r, ll v, ll tl, ll tr) { if (l <= tl && tr <= r) return tree1[v]; if (tl > r || tr < l) return 0; ll tm = (tl+tr)/2; return get(l, r, v*2, tl, tm)+get(l, r, v*2+1, tm+1, tr); } void update(ll idx, ll val, ll v, ll tl, ll tr) { if (tl == tr) { tree1[v] = val; return; } ll tm = (tl+tr)/2; if (idx <= tm) update(idx, val, v*2, tl, tm); else update(idx, val, v*2+1, tm+1, tr); tree1[v] = tree1[v*2]+tree1[v*2+1]; }*/ int main() { ll n; cin >> n; vll a(n); ll s = 0; for (int i =0; i < n; i ++) { cin >> a[i]; s += a[i]; } if (s % 2 == 1) { cout << 0 << endl; return 0; } else { bitset<250007> dp; dp.set(0); for (int j = 0; j < n; j ++) { bitset<250007> dp1; dp1 = dp; dp1 <<= a[j]; /*for (int i1 = 0; i1 <= 10; i1 ++) { if (dp1[i1]) cout << 1; else cout << 0; } cout << endl;*/ dp |= dp1; } if (!dp[s/2]) { cout << 0 << endl; return 0; } } bitset<250007> sm; for (int i = 0; i <= s; i ++) { sm.set(i); } for(int i = 0; i < n; i ++) { bitset<250007> dp; dp.set(0); for (int j = 0; j < n; j ++) { if (i == j) continue; bitset<250007> dp1; dp1 = dp; dp1 <<= a[j]; /*for (int i1 = 0; i1 <= 10; i1 ++) { if (dp1[i1]) cout << 1; else cout << 0; } cout << endl;*/ dp |= dp1; } bitset<250007> us1; for (int j = 1; j <= s-a[i]; j ++) { //if (j == s-a[i]) continue; if (dp[j]) { ll k = abs(s-a[i]-2*j); //cout << k << endl; us1.set(k); } } sm &= us1; } vll res; for (int i = 1; i <= 250007; i ++) { if (sm[i]) res.pb(i); } cout << res.size() << endl; for (int i : res) { cout << i << ' '; } cout << endl; }
#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...