oj.uz

Submission #332996

# Submission time Handle Problem Language Result Execution time Memory
332996 2020-12-04T08:36:26 Z Dymo Bootfall (IZhO17_bootfall) C++14
0 / 100
 2 ms 876 KB 
#include<bits/stdc++.h>
using namespace std;


#define pb    push_back
#define eb   emplace_back
#define ll  long long
#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);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //https://oj.uz/problem/view/APIO19_bridges
    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];
     }
     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

bootfall.cpp: In function 'int main()':
bootfall.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   61 |         freopen("queue.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   62 |         freopen("queue.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Incorrect 2 ms 748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Incorrect 2 ms 748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Incorrect 2 ms 748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Incorrect 2 ms 748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Incorrect 2 ms 748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Incorrect 2 ms 748 KB Output isn't correct
4 Halted 0 ms 0 KB -