oj.uz

Submission #173200

# Submission time Handle Problem Language Result Execution time Memory
173200 2020-01-03T14:52:27 Z DeD_TihoN Bootfall (IZhO17_bootfall) C++14
13 / 100
 1000 ms 6168 KB 
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define ull unsigned long long
#define endl '\n'
#define y1 yaumru
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define iter vector<int>::iterator
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=500+2;
const int inf=1e9+1e9;
const int mod=1e9+7;
const ld eps=1e-9;
const int M=250000+1;

bitset<M>dp[N];
bitset<M>pref[N];
bitset<M>suf[N];
int a[N];

main ()
{
    ios;
    int n;
    cin>>n;
    for (int i=1;i<=n;++i){
        cin>>a[i];
    }
    int sum=0;
    for (int i=1;i<=n;++i){
        sum+=a[i];
    }
    if (sum%2==1){
        cout<<0<<endl;
        exit(0);
    }
    pref[0][0]=1;
    suf[n+1][0]=1;
    for (int i=1;i<=n;++i){
        pref[i]=(pref[i-1]|(pref[i-1]<<a[i]));
    }
    for (int i=n;i>=1;--i){
        suf[i]=(suf[i+1]|(suf[i+1]<<a[i]));
    }
    for (int i=0;i<=n;++i){
        dp[i]=suf[i+1];
        if (i!=0){
            for (int j=pref[i-1]._Find_first();j<M;j=pref[i-1]._Find_next(j)){
                bitset<M>f=(suf[i+1]<<j);
                dp[i]=(dp[i]|f);
            }
        }
    }
//    for (int j=0;j<=10;++j){
//        cout<<dp[0][j]<<' ';
//    }
    vector<int>ans;
    if (dp[0][sum/2]==0){
        cout<<0<<endl;
        exit(0);
    }
    for (int i=1;i<=M;++i){
        bool cc=true;
        for (int j=1;j<=n;++j){
            if ((sum-a[j]+i)%2==1){
                cc=false;
                break;
            }
            if ((sum-a[j]+i)%2==0){
                if (dp[j][(sum-a[j]+i)/2]==0){
                    cc=false;
                    break;
                }
            }
        }
        if (cc)ans.pb(i);
    }
    cout<<(int)ans.size()<<endl;
    for (int i=0;i<ans.size();++i){
        cout<<ans[i]<<' ';
    }
}

Compilation message

bootfall.cpp:43:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
bootfall.cpp: In function 'int main()':
bootfall.cpp:101:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<ans.size();++i){
                  ~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 2 ms 808 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 31 ms 1628 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 4 ms 1144 KB Output is correct
8 Correct 28 ms 1656 KB Output is correct
9 Correct 15 ms 1528 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 2 ms 808 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 31 ms 1628 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 4 ms 1144 KB Output is correct
8 Correct 28 ms 1656 KB Output is correct
9 Correct 15 ms 1528 KB Output is correct
10 Correct 13 ms 3320 KB Output is correct
11 Correct 62 ms 3296 KB Output is correct
12 Correct 46 ms 3340 KB Output is correct
13 Correct 50 ms 2936 KB Output is correct
14 Correct 60 ms 3064 KB Output is correct
15 Correct 43 ms 3260 KB Output is correct
16 Correct 50 ms 3316 KB Output is correct
17 Correct 24 ms 2168 KB Output is correct
18 Correct 42 ms 2808 KB Output is correct
19 Correct 42 ms 2936 KB Output is correct
20 Correct 13 ms 3320 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 2 ms 808 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 31 ms 1628 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 4 ms 1144 KB Output is correct
8 Correct 28 ms 1656 KB Output is correct
9 Correct 15 ms 1528 KB Output is correct
10 Correct 13 ms 3320 KB Output is correct
11 Correct 62 ms 3296 KB Output is correct
12 Correct 46 ms 3340 KB Output is correct
13 Correct 50 ms 2936 KB Output is correct
14 Correct 60 ms 3064 KB Output is correct
15 Correct 43 ms 3260 KB Output is correct
16 Correct 50 ms 3316 KB Output is correct
17 Correct 24 ms 2168 KB Output is correct
18 Correct 42 ms 2808 KB Output is correct
19 Correct 42 ms 2936 KB Output is correct
20 Correct 13 ms 3320 KB Output is correct
21 Execution timed out 1055 ms 6168 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 2 ms 808 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 31 ms 1628 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 4 ms 1144 KB Output is correct
8 Correct 28 ms 1656 KB Output is correct
9 Correct 15 ms 1528 KB Output is correct
10 Correct 13 ms 3320 KB Output is correct
11 Correct 62 ms 3296 KB Output is correct
12 Correct 46 ms 3340 KB Output is correct
13 Correct 50 ms 2936 KB Output is correct
14 Correct 60 ms 3064 KB Output is correct
15 Correct 43 ms 3260 KB Output is correct
16 Correct 50 ms 3316 KB Output is correct
17 Correct 24 ms 2168 KB Output is correct
18 Correct 42 ms 2808 KB Output is correct
19 Correct 42 ms 2936 KB Output is correct
20 Correct 13 ms 3320 KB Output is correct
21 Execution timed out 1055 ms 6168 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 2 ms 808 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 31 ms 1628 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 4 ms 1144 KB Output is correct
8 Correct 28 ms 1656 KB Output is correct
9 Correct 15 ms 1528 KB Output is correct
10 Correct 13 ms 3320 KB Output is correct
11 Correct 62 ms 3296 KB Output is correct
12 Correct 46 ms 3340 KB Output is correct
13 Correct 50 ms 2936 KB Output is correct
14 Correct 60 ms 3064 KB Output is correct
15 Correct 43 ms 3260 KB Output is correct
16 Correct 50 ms 3316 KB Output is correct
17 Correct 24 ms 2168 KB Output is correct
18 Correct 42 ms 2808 KB Output is correct
19 Correct 42 ms 2936 KB Output is correct
20 Correct 13 ms 3320 KB Output is correct
21 Execution timed out 1055 ms 6168 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 2 ms 808 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 31 ms 1628 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 4 ms 1144 KB Output is correct
8 Correct 28 ms 1656 KB Output is correct
9 Correct 15 ms 1528 KB Output is correct
10 Correct 13 ms 3320 KB Output is correct
11 Correct 62 ms 3296 KB Output is correct
12 Correct 46 ms 3340 KB Output is correct
13 Correct 50 ms 2936 KB Output is correct
14 Correct 60 ms 3064 KB Output is correct
15 Correct 43 ms 3260 KB Output is correct
16 Correct 50 ms 3316 KB Output is correct
17 Correct 24 ms 2168 KB Output is correct
18 Correct 42 ms 2808 KB Output is correct
19 Correct 42 ms 2936 KB Output is correct
20 Correct 13 ms 3320 KB Output is correct
21 Execution timed out 1055 ms 6168 KB Time limit exceeded
22 Halted 0 ms 0 KB -