oj.uz

Submission #858324

# Submission time Handle Problem Language Result Execution time Memory
858324 2023-10-08T06:18:30 Z nnhzzz Bootfall (IZhO17_bootfall) C++14
13 / 100
 1000 ms 564 KB 
// cre: Nguyen Ngoc Hung - Train VOI 2024 :>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define                fi  first
#define                se  second
#define                ll  long long
#define                vi  vector<int>
#define               vvi  vector<vi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define REPDIS(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     REPD(i,be,en)  for(int i = (be); i>=(en); i--)
#define      REP(i,be,en)  for(int i = (be); i<=(en); i++)
//-------------------------------------------------------------//
const int oo = 1e9,LOG = 20,MAXN = 5e5+7,N = 250007;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

void solve(){
    int s = 0,n; cin >> n;
    vi a(n+1);
    bitset<N> tmp; tmp[0] = 1;
    REP(i,1,n){
        cin >> a[i];
        s += a[i];
        tmp |= tmp<<a[i];
    }
    if(s%2==1 || tmp[s/2]==0){
        cout << 0; return ;
    }
    vi res;
    REP(k,1,s){
        int ok = 1;
        REP(j,1,n){
            int t = s-a[j]+k;
            if(t%2==1){
                ok = 0; break;
            }
            bitset<N> dp(0); dp[0] = dp[k] = 1;
            REP(i,1,n){
                if(i==j) continue;
                dp |= dp<<a[i];
            }
            if(dp[t/2]==0){
                ok = 0; break;
            }
        }
        if(ok==1) res.push_back(k);
    }
    cout << SZ(res) << "\n";
    for(auto &i:res){
        cout << i << " ";
    }
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define name "test"
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    #define name1 "nnhzzz"
    if(fopen(name1".inp","r")){
        freopen(name1".inp","r",stdin);
        freopen(name1".out","w",stdout);
    }

    int test = 1;

    while(test--){
      solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 144 ms 348 KB Output is correct
6 Correct 8 ms 348 KB Output is correct
7 Correct 7 ms 348 KB Output is correct
8 Correct 175 ms 348 KB Output is correct
9 Correct 14 ms 564 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 144 ms 348 KB Output is correct
6 Correct 8 ms 348 KB Output is correct
7 Correct 7 ms 348 KB Output is correct
8 Correct 175 ms 348 KB Output is correct
9 Correct 14 ms 564 KB Output is correct
10 Correct 114 ms 548 KB Output is correct
11 Correct 562 ms 348 KB Output is correct
12 Correct 46 ms 344 KB Output is correct
13 Correct 33 ms 344 KB Output is correct
14 Correct 557 ms 548 KB Output is correct
15 Correct 425 ms 556 KB Output is correct
16 Correct 612 ms 548 KB Output is correct
17 Correct 144 ms 548 KB Output is correct
18 Correct 341 ms 348 KB Output is correct
19 Correct 309 ms 548 KB Output is correct
20 Correct 125 ms 544 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 144 ms 348 KB Output is correct
6 Correct 8 ms 348 KB Output is correct
7 Correct 7 ms 348 KB Output is correct
8 Correct 175 ms 348 KB Output is correct
9 Correct 14 ms 564 KB Output is correct
10 Correct 114 ms 548 KB Output is correct
11 Correct 562 ms 348 KB Output is correct
12 Correct 46 ms 344 KB Output is correct
13 Correct 33 ms 344 KB Output is correct
14 Correct 557 ms 548 KB Output is correct
15 Correct 425 ms 556 KB Output is correct
16 Correct 612 ms 548 KB Output is correct
17 Correct 144 ms 548 KB Output is correct
18 Correct 341 ms 348 KB Output is correct
19 Correct 309 ms 548 KB Output is correct
20 Correct 125 ms 544 KB Output is correct
21 Execution timed out 1068 ms 348 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 144 ms 348 KB Output is correct
6 Correct 8 ms 348 KB Output is correct
7 Correct 7 ms 348 KB Output is correct
8 Correct 175 ms 348 KB Output is correct
9 Correct 14 ms 564 KB Output is correct
10 Correct 114 ms 548 KB Output is correct
11 Correct 562 ms 348 KB Output is correct
12 Correct 46 ms 344 KB Output is correct
13 Correct 33 ms 344 KB Output is correct
14 Correct 557 ms 548 KB Output is correct
15 Correct 425 ms 556 KB Output is correct
16 Correct 612 ms 548 KB Output is correct
17 Correct 144 ms 548 KB Output is correct
18 Correct 341 ms 348 KB Output is correct
19 Correct 309 ms 548 KB Output is correct
20 Correct 125 ms 544 KB Output is correct
21 Execution timed out 1068 ms 348 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 144 ms 348 KB Output is correct
6 Correct 8 ms 348 KB Output is correct
7 Correct 7 ms 348 KB Output is correct
8 Correct 175 ms 348 KB Output is correct
9 Correct 14 ms 564 KB Output is correct
10 Correct 114 ms 548 KB Output is correct
11 Correct 562 ms 348 KB Output is correct
12 Correct 46 ms 344 KB Output is correct
13 Correct 33 ms 344 KB Output is correct
14 Correct 557 ms 548 KB Output is correct
15 Correct 425 ms 556 KB Output is correct
16 Correct 612 ms 548 KB Output is correct
17 Correct 144 ms 548 KB Output is correct
18 Correct 341 ms 348 KB Output is correct
19 Correct 309 ms 548 KB Output is correct
20 Correct 125 ms 544 KB Output is correct
21 Execution timed out 1068 ms 348 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 144 ms 348 KB Output is correct
6 Correct 8 ms 348 KB Output is correct
7 Correct 7 ms 348 KB Output is correct
8 Correct 175 ms 348 KB Output is correct
9 Correct 14 ms 564 KB Output is correct
10 Correct 114 ms 548 KB Output is correct
11 Correct 562 ms 348 KB Output is correct
12 Correct 46 ms 344 KB Output is correct
13 Correct 33 ms 344 KB Output is correct
14 Correct 557 ms 548 KB Output is correct
15 Correct 425 ms 556 KB Output is correct
16 Correct 612 ms 548 KB Output is correct
17 Correct 144 ms 548 KB Output is correct
18 Correct 341 ms 348 KB Output is correct
19 Correct 309 ms 548 KB Output is correct
20 Correct 125 ms 544 KB Output is correct
21 Execution timed out 1068 ms 348 KB Time limit exceeded
22 Halted 0 ms 0 KB -