Submission #954315

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
954315	2024-03-27T15:40:00 Z	nguyennh	Bootfall (IZhO17_bootfall)	C++14	13 / 100	7 ms	2652 KB

bootfall

#include<bits/stdc++.h>
#define el '\n'
using namespace std ;

const int MN = 2e5 + 50;

int n;

namespace sub_trau{
  int64_t dp[MN];
  
  // check whether existing a way to divide array into 2 parts with sum = x;
  void solve(){
    vector<int> a(n + 5);
    for ( int i = 1 ; i <= n ; i++ ) cin >> a[i];
    if (n & 1){
      cout << 0;
      return;
    }
    bool odd = false , even = false;
    for ( int i = 1 ; i <= n ; i++ ){
      odd |= (a[i] & 1);
      even |= (a[i] % 2 == 0);
    }
    if (odd && even){
      cout << 0;
      return;
    }
    int sum = accumulate(a.begin() + 1 , a.begin() + n + 1 , 0);
    int mn = *min_element(a.begin() + 1 , a.begin() + n + 1); 
    dp[0] = 1;
    for ( int i = 1 ; i <= n ; i++ ){
      for ( int j = sum ; j >= a[i] ; j-- ) dp[j] += dp[j - a[i]];
    }
    if (!dp[sum / 2] || (sum & 1)){
      cout << 0;
      return;
    }
    vector<int> ans , candidates;
    for ( int i = 1 ; i <= n ; i++ ) candidates.push_back(a[i]);
    for ( int val = odd ? 1 : 2 ; val <= sum - mn ; val += 2 ){
      int all = sum + val;
      candidates.push_back(val);
      for ( int j = all ; j >= val ; j-- ) dp[j] += dp[j - val];
      bool check = true;
      for ( int turn = 0 ; turn < n ; turn++ ){
        if (!check) break;
        int need = all - candidates[turn];
        if (need & 1){
          check = false;
          break;  
        }
        for ( int j = candidates[turn] ; j <= need / 2 ; j++ ){
          dp[j] -= dp[j - candidates[turn]];
        }
        if (!dp[need / 2]){
          check = false;
        }
        for ( int j = need / 2 ; j >= candidates[turn] ; j-- ) dp[j] += dp[j - candidates[turn]];
      }
      if (check) ans.push_back(val);
      candidates.pop_back();
      for ( int j = val ; j <= all ; j++ ) dp[j] -= dp[j - val];
    }
    cout << ans.size() << el;
    for ( auto x : ans ) cout << x << " ";
  }
}

namespace sub_final{
  int64_t dp[MN];
  bool choose[MN];
  
  void solve(){
    vector<int> a(n + 5);
    for ( int i = 1 ; i <= n ; i++ ) cin >> a[i];
    if (n & 1){
      cout << 0;
      return;
    }
    bool odd = false , even = false;
    for ( int i = 1 ; i <= n ; i++ ){
      odd |= (a[i] & 1);
      even |= (a[i] % 2 == 0);
    }
    if (odd && even){
      cout << 0;
      return;
    }
    int sum = accumulate(a.begin() + 1 , a.begin() + n + 1 , 0);
    dp[0] = 1;
    for ( int i = 1 ; i <= n ; i++ ){
      for ( int j = sum ; j >= a[i] ; j-- ) dp[j] += dp[j - a[i]];
    }
    if (!dp[sum / 2] || (sum & 1)){
      cout << 0;
      return;
    }
    memset(choose , true , sizeof(choose));
    for ( int i = odd ? 2 : 1 ; i <= sum ; i += 2 ) choose[i] = false;
    for ( int i = 1 ; i <= n ; i++ ){
      vector<int64_t> ndp(sum + 5);
      for ( int j = 0 ; j <= sum ; j++ ) ndp[j] = dp[j];
      for ( int j = a[i] ; j <= sum ; j++ ) ndp[j] -= ndp[j - a[i]];
      for ( int val = odd ? 1 : 2 ; val <= sum ; val += 2 ){
        int new_sum = sum - a[i] + val;
        if ((new_sum & 1) || (new_sum / 2 < val) || !dp[new_sum / 2 - val]) choose[val] = false; 
      }
    }
    vector<int> ans;
    for ( int i = 1 ; i <= sum ; i++ ){
      if (choose[i]) ans.push_back(i);
    }
    cout << ans.size() << el;
    for ( auto x : ans ) cout << x << " ";
  }
}

int32_t main (){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  if (n <= 30) sub_trau::solve();
  else sub_final::solve();
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	2 ms	2396 KB	Output is correct
5	Correct	2 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	7 ms	2396 KB	Output is correct
9	Correct	0 ms	600 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	2 ms	2396 KB	Output is correct
5	Correct	2 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	7 ms	2396 KB	Output is correct
9	Correct	0 ms	600 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	2 ms	2396 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	2 ms	2392 KB	Output is correct
15	Correct	2 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	2 ms	2396 KB	Output is correct

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	2 ms	2396 KB	Output is correct
5	Correct	2 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	7 ms	2396 KB	Output is correct
9	Correct	0 ms	600 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	2 ms	2396 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	2 ms	2392 KB	Output is correct
15	Correct	2 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	2 ms	2396 KB	Output is correct
21	Correct	1 ms	2648 KB	Output is correct
22	Correct	1 ms	2652 KB	Output is correct
23	Correct	1 ms	2652 KB	Output is correct
24	Correct	3 ms	2648 KB	Output is correct
25	Incorrect	2 ms	2652 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #4
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	2 ms	2396 KB	Output is correct
5	Correct	2 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	7 ms	2396 KB	Output is correct
9	Correct	0 ms	600 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	2 ms	2396 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	2 ms	2392 KB	Output is correct
15	Correct	2 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	2 ms	2396 KB	Output is correct
21	Correct	1 ms	2648 KB	Output is correct
22	Correct	1 ms	2652 KB	Output is correct
23	Correct	1 ms	2652 KB	Output is correct
24	Correct	3 ms	2648 KB	Output is correct
25	Incorrect	2 ms	2652 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	2 ms	2396 KB	Output is correct
5	Correct	2 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	7 ms	2396 KB	Output is correct
9	Correct	0 ms	600 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	2 ms	2396 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	2 ms	2392 KB	Output is correct
15	Correct	2 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	2 ms	2396 KB	Output is correct
21	Correct	1 ms	2648 KB	Output is correct
22	Correct	1 ms	2652 KB	Output is correct
23	Correct	1 ms	2652 KB	Output is correct
24	Correct	3 ms	2648 KB	Output is correct
25	Incorrect	2 ms	2652 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	2 ms	2396 KB	Output is correct
5	Correct	2 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	7 ms	2396 KB	Output is correct
9	Correct	0 ms	600 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	2 ms	2396 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	2 ms	2392 KB	Output is correct
15	Correct	2 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	2 ms	2396 KB	Output is correct
21	Correct	1 ms	2648 KB	Output is correct
22	Correct	1 ms	2652 KB	Output is correct
23	Correct	1 ms	2652 KB	Output is correct
24	Correct	3 ms	2648 KB	Output is correct
25	Incorrect	2 ms	2652 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Submission #954315

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 15.0

Subtask #4 0 / 16.0

Subtask #5 0 / 21.0

Subtask #6 0 / 35.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 15.0

Subtask #4
0 / 16.0

Subtask #5
0 / 21.0

Subtask #6
0 / 35.0