oj.uz

Submission #874178

# Submission time Handle Problem Language Result Execution time Memory
874178 2023-11-16T11:58:10 Z elotelo966 Bootfall (IZhO17_bootfall) C++17
13 / 100
 1000 ms 484 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY 1000000005
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mid (start+end)/2
#define lim 600005
#define se second
#define fi first

inline bool ol(vector<int> &dizi,int cev){
    //vector<bool> tut(cev+5,0);
    bitset <250005> tut;
    tut[0]=1;
    bool stop=true;
    for(int i=0;i<dizi.size() && stop;i++){
        for(int j=cev/2;j>=dizi[i];j--){
            tut[j]=tut[j]|tut[j-dizi[i]];
            if(tut[cev/2]){stop=false;break;}
           // cout<<j<<" "<<tut[j]<<endl;
        }
    }
    return tut[cev/2];
}

int32_t main(){
    faster
    //freopen("bootfall.in","r",stdin);
    //freopen("bootfall.out","w",stdout);
    int n;cin>>n;
    vector<int> dizi(n);
    int cev=0;
    for(int i=0;i<n;i++){
        cin>>dizi[i];
        cev+=dizi[i];
    }
    if((cev&1) || (ol(dizi,cev))==0){
        cout<<0<<'\n';
        return 0;
    }
    vector<int> ans;
    for(int i=1;i<=cev;i++){
        vector<int> huh=dizi;
        int hum=cev;
        bool kom=1;
        for(int j=0;j<n;j++){
            huh[j]=i;
            hum+=i-dizi[j];
            if(!(hum&1))kom&=ol(huh,hum);
            else{
                kom=0;
                break;
            }
            hum=cev;
            huh[j]=dizi[j];
        }
        if(kom)ans.push_back(i);
    }
    cout<<ans.size()<<'\n';
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
    cout<<'\n';
    return 0;
}

Compilation message

bootfall.cpp: In function 'bool ol(std::vector<long long int>&, long long int)':
bootfall.cpp:19:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=0;i<dizi.size() && stop;i++){
      |                 ~^~~~~~~~~~~~
bootfall.cpp: In function 'int32_t main()':
bootfall.cpp:63:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0;i<ans.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 480 KB Output is correct
5 Correct 89 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 299 ms 484 KB Output is correct
9 Correct 3 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 480 KB Output is correct
5 Correct 89 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 299 ms 484 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 294 ms 348 KB Output is correct
11 Correct 33 ms 348 KB Output is correct
12 Correct 108 ms 460 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 39 ms 348 KB Output is correct
15 Correct 23 ms 348 KB Output is correct
16 Correct 34 ms 348 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 21 ms 348 KB Output is correct
19 Correct 15 ms 344 KB Output is correct
20 Correct 327 ms 460 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 480 KB Output is correct
5 Correct 89 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 299 ms 484 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 294 ms 348 KB Output is correct
11 Correct 33 ms 348 KB Output is correct
12 Correct 108 ms 460 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 39 ms 348 KB Output is correct
15 Correct 23 ms 348 KB Output is correct
16 Correct 34 ms 348 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 21 ms 348 KB Output is correct
19 Correct 15 ms 344 KB Output is correct
20 Correct 327 ms 460 KB Output is correct
21 Execution timed out 1063 ms 452 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 480 KB Output is correct
5 Correct 89 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 299 ms 484 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 294 ms 348 KB Output is correct
11 Correct 33 ms 348 KB Output is correct
12 Correct 108 ms 460 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 39 ms 348 KB Output is correct
15 Correct 23 ms 348 KB Output is correct
16 Correct 34 ms 348 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 21 ms 348 KB Output is correct
19 Correct 15 ms 344 KB Output is correct
20 Correct 327 ms 460 KB Output is correct
21 Execution timed out 1063 ms 452 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 480 KB Output is correct
5 Correct 89 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 299 ms 484 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 294 ms 348 KB Output is correct
11 Correct 33 ms 348 KB Output is correct
12 Correct 108 ms 460 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 39 ms 348 KB Output is correct
15 Correct 23 ms 348 KB Output is correct
16 Correct 34 ms 348 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 21 ms 348 KB Output is correct
19 Correct 15 ms 344 KB Output is correct
20 Correct 327 ms 460 KB Output is correct
21 Execution timed out 1063 ms 452 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 480 KB Output is correct
5 Correct 89 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 299 ms 484 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 294 ms 348 KB Output is correct
11 Correct 33 ms 348 KB Output is correct
12 Correct 108 ms 460 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 39 ms 348 KB Output is correct
15 Correct 23 ms 348 KB Output is correct
16 Correct 34 ms 348 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 21 ms 348 KB Output is correct
19 Correct 15 ms 344 KB Output is correct
20 Correct 327 ms 460 KB Output is correct
21 Execution timed out 1063 ms 452 KB Time limit exceeded
22 Halted 0 ms 0 KB -