Submission #333006

#TimeUsernameProblemLanguageResultExecution timeMemory
333006DymoBootfall (IZhO17_bootfall)C++14
100 / 100
219 ms2924 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define eb emplace_back #define ll int #define pll pair<ll,ll> #define ff first #define ss second #define endl "\n" const ll maxn=500*500+10; const ll mod =1e9+7 ; const ll base=1e18; const ll block=1000; /// con 0 ngay nua /// zesitahn ll a[maxn]; bitset<maxn> st1; ll t=0; void dosth(ll l,ll r,bitset<maxn> st) { if (l==r) { bitset<maxn>chk; for (int i=1;i<maxn;i++) { ll cl=t-a[l]-i; if (cl<0) break; if (cl%2==0) { cl/=2; if (st[cl]==1) chk[i]=1; } } st1&=chk; return ; } ll mid=(l+r)/2; auto nxt=st; for (int i=mid+1;i<=r;i++) { nxt|=(nxt<<a[i]); } dosth(l,mid,nxt); nxt=st; for (int i=l;i<=mid;i++) { nxt|=(nxt<<a[i]); } dosth(mid+1, r, nxt); } bool chk(ll n) { if (t%2==1) return false; bitset<maxn> st; st[0]=1; for (int i=1;i<=n;i++) { st|=(st<<a[i]); } // cout <<t/2<<endl; return st[t/2]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("queue.inp", "r")) { freopen("queue.inp", "r", stdin); freopen("queue.out", "w", stdout); } ll n; cin>> n; for (int i=1;i<=n;i++) { cin>>a[i]; t+=a[i]; } if (!chk(n)) { cout <<0; return 0; } bitset<maxn> st; st[0]=1; for (int i=1;i<maxn;i++) { st1[i]=1; } dosth(1,n,st); vector<ll> ans; for (int i=1;i<maxn;i++) { if (st1[i]) ans.pb(i); } cout <<ans.size()<<endl; for (auto to:ans) { cout <<to<<" "; } }

Compilation message (stderr)

bootfall.cpp:14:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const ll base=1e18;
      |               ^~~~
bootfall.cpp: In function 'int main()':
bootfall.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   73 |         freopen("queue.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   74 |         freopen("queue.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...