oj.uz

Submission #858311

# Submission time Handle Problem Language Result Execution time Memory
858311 2023-10-08T05:44:07 Z nnhzzz Bootfall (IZhO17_bootfall) C++14
13 / 100
 1000 ms 592 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 = 6e4;
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[30000] = 1;
    REP(i,1,n){
        cin >> a[i];
        s += a[i];
        tmp = (tmp<<a[i])|(tmp>>a[i]);
    }
    if(tmp[30000]==0){
        cout << 0; return ;
    }
    vi res;
    REP(k,1,s){
        int ok = 1;
        REP(j,1,n){
            bitset<N> dp;
            dp[s] = 1;
            dp = (dp<<k)|(dp>>k);
            REP(i,1,n){
                if(i==j) continue;
                dp = (dp<<a[i])|(dp>>a[i]);
            }
            if(dp[s]==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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 93 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 96 ms 344 KB Output is correct
9 Correct 15 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 93 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 96 ms 344 KB Output is correct
9 Correct 15 ms 344 KB Output is correct
10 Correct 71 ms 472 KB Output is correct
11 Correct 273 ms 468 KB Output is correct
12 Correct 35 ms 492 KB Output is correct
13 Correct 28 ms 348 KB Output is correct
14 Correct 242 ms 464 KB Output is correct
15 Correct 194 ms 592 KB Output is correct
16 Correct 247 ms 464 KB Output is correct
17 Correct 64 ms 348 KB Output is correct
18 Correct 152 ms 468 KB Output is correct
19 Correct 142 ms 348 KB Output is correct
20 Correct 67 ms 344 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 93 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 96 ms 344 KB Output is correct
9 Correct 15 ms 344 KB Output is correct
10 Correct 71 ms 472 KB Output is correct
11 Correct 273 ms 468 KB Output is correct
12 Correct 35 ms 492 KB Output is correct
13 Correct 28 ms 348 KB Output is correct
14 Correct 242 ms 464 KB Output is correct
15 Correct 194 ms 592 KB Output is correct
16 Correct 247 ms 464 KB Output is correct
17 Correct 64 ms 348 KB Output is correct
18 Correct 152 ms 468 KB Output is correct
19 Correct 142 ms 348 KB Output is correct
20 Correct 67 ms 344 KB Output is correct
21 Execution timed out 1053 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 93 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 96 ms 344 KB Output is correct
9 Correct 15 ms 344 KB Output is correct
10 Correct 71 ms 472 KB Output is correct
11 Correct 273 ms 468 KB Output is correct
12 Correct 35 ms 492 KB Output is correct
13 Correct 28 ms 348 KB Output is correct
14 Correct 242 ms 464 KB Output is correct
15 Correct 194 ms 592 KB Output is correct
16 Correct 247 ms 464 KB Output is correct
17 Correct 64 ms 348 KB Output is correct
18 Correct 152 ms 468 KB Output is correct
19 Correct 142 ms 348 KB Output is correct
20 Correct 67 ms 344 KB Output is correct
21 Execution timed out 1053 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 93 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 96 ms 344 KB Output is correct
9 Correct 15 ms 344 KB Output is correct
10 Correct 71 ms 472 KB Output is correct
11 Correct 273 ms 468 KB Output is correct
12 Correct 35 ms 492 KB Output is correct
13 Correct 28 ms 348 KB Output is correct
14 Correct 242 ms 464 KB Output is correct
15 Correct 194 ms 592 KB Output is correct
16 Correct 247 ms 464 KB Output is correct
17 Correct 64 ms 348 KB Output is correct
18 Correct 152 ms 468 KB Output is correct
19 Correct 142 ms 348 KB Output is correct
20 Correct 67 ms 344 KB Output is correct
21 Execution timed out 1053 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 93 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 96 ms 344 KB Output is correct
9 Correct 15 ms 344 KB Output is correct
10 Correct 71 ms 472 KB Output is correct
11 Correct 273 ms 468 KB Output is correct
12 Correct 35 ms 492 KB Output is correct
13 Correct 28 ms 348 KB Output is correct
14 Correct 242 ms 464 KB Output is correct
15 Correct 194 ms 592 KB Output is correct
16 Correct 247 ms 464 KB Output is correct
17 Correct 64 ms 348 KB Output is correct
18 Correct 152 ms 468 KB Output is correct
19 Correct 142 ms 348 KB Output is correct
20 Correct 67 ms 344 KB Output is correct
21 Execution timed out 1053 ms 348 KB Time limit exceeded
22 Halted 0 ms 0 KB -