답안 #58453 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58453	2018-07-17T22:29:05 Z	Benq	Bootfall (IZhO17_bootfall)	C++14	28 / 100	1000 ms	1292 KB

bootfall

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

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

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 500*500;

typedef bitset<2*MX+1> B;

int N, a[500];
B all;
bitset<500> al;

B gen(bitset<500> tmp) {
    B b; b[MX] = 1;
    F0R(i,N) if (tmp[i]) b = (b<<a[i])|(b>>a[i]);
    return b;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    all.flip(); al.flip();
    cin >> N;
    F0R(i,N) cin >> a[i];
    if (gen(al)[MX] == 0) {
        cout << 0;
        exit(0);
    }
    F0R(i,N) {
        al[i] = 0;
        all &= gen(al);
        al[i] = 1;
    }
    vi v;
    FOR(i,1,MX+1) if (all[MX+i]) v.pb(i);
    cout << sz(v) << "\n";
    for (int i: v) cout << i << " ";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	760 KB	Output is correct
2	Correct	7 ms	760 KB	Output is correct
3	Correct	4 ms	864 KB	Output is correct
4	Correct	5 ms	920 KB	Output is correct
5	Correct	15 ms	952 KB	Output is correct
6	Correct	12 ms	952 KB	Output is correct
7	Correct	9 ms	952 KB	Output is correct
8	Correct	14 ms	952 KB	Output is correct
9	Correct	10 ms	1020 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	760 KB	Output is correct
2	Correct	7 ms	760 KB	Output is correct
3	Correct	4 ms	864 KB	Output is correct
4	Correct	5 ms	920 KB	Output is correct
5	Correct	15 ms	952 KB	Output is correct
6	Correct	12 ms	952 KB	Output is correct
7	Correct	9 ms	952 KB	Output is correct
8	Correct	14 ms	952 KB	Output is correct
9	Correct	10 ms	1020 KB	Output is correct
10	Correct	74 ms	1020 KB	Output is correct
11	Correct	82 ms	1020 KB	Output is correct
12	Correct	89 ms	1032 KB	Output is correct
13	Correct	54 ms	1032 KB	Output is correct
14	Correct	60 ms	1168 KB	Output is correct
15	Correct	63 ms	1168 KB	Output is correct
16	Correct	84 ms	1168 KB	Output is correct
17	Correct	27 ms	1168 KB	Output is correct
18	Correct	61 ms	1168 KB	Output is correct
19	Correct	60 ms	1168 KB	Output is correct
20	Correct	89 ms	1168 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	760 KB	Output is correct
2	Correct	7 ms	760 KB	Output is correct
3	Correct	4 ms	864 KB	Output is correct
4	Correct	5 ms	920 KB	Output is correct
5	Correct	15 ms	952 KB	Output is correct
6	Correct	12 ms	952 KB	Output is correct
7	Correct	9 ms	952 KB	Output is correct
8	Correct	14 ms	952 KB	Output is correct
9	Correct	10 ms	1020 KB	Output is correct
10	Correct	74 ms	1020 KB	Output is correct
11	Correct	82 ms	1020 KB	Output is correct
12	Correct	89 ms	1032 KB	Output is correct
13	Correct	54 ms	1032 KB	Output is correct
14	Correct	60 ms	1168 KB	Output is correct
15	Correct	63 ms	1168 KB	Output is correct
16	Correct	84 ms	1168 KB	Output is correct
17	Correct	27 ms	1168 KB	Output is correct
18	Correct	61 ms	1168 KB	Output is correct
19	Correct	60 ms	1168 KB	Output is correct
20	Correct	89 ms	1168 KB	Output is correct
21	Correct	377 ms	1168 KB	Output is correct
22	Correct	420 ms	1168 KB	Output is correct
23	Correct	182 ms	1204 KB	Output is correct
24	Correct	710 ms	1208 KB	Output is correct
25	Correct	874 ms	1244 KB	Output is correct
26	Correct	836 ms	1244 KB	Output is correct
27	Correct	960 ms	1252 KB	Output is correct
28	Correct	933 ms	1256 KB	Output is correct
29	Correct	833 ms	1256 KB	Output is correct
30	Correct	762 ms	1264 KB	Output is correct
31	Correct	815 ms	1268 KB	Output is correct
32	Correct	845 ms	1268 KB	Output is correct
33	Correct	758 ms	1268 KB	Output is correct
34	Correct	785 ms	1280 KB	Output is correct
35	Correct	753 ms	1284 KB	Output is correct
36	Correct	792 ms	1292 KB	Output is correct

Subtask #4
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	760 KB	Output is correct
2	Correct	7 ms	760 KB	Output is correct
3	Correct	4 ms	864 KB	Output is correct
4	Correct	5 ms	920 KB	Output is correct
5	Correct	15 ms	952 KB	Output is correct
6	Correct	12 ms	952 KB	Output is correct
7	Correct	9 ms	952 KB	Output is correct
8	Correct	14 ms	952 KB	Output is correct
9	Correct	10 ms	1020 KB	Output is correct
10	Correct	74 ms	1020 KB	Output is correct
11	Correct	82 ms	1020 KB	Output is correct
12	Correct	89 ms	1032 KB	Output is correct
13	Correct	54 ms	1032 KB	Output is correct
14	Correct	60 ms	1168 KB	Output is correct
15	Correct	63 ms	1168 KB	Output is correct
16	Correct	84 ms	1168 KB	Output is correct
17	Correct	27 ms	1168 KB	Output is correct
18	Correct	61 ms	1168 KB	Output is correct
19	Correct	60 ms	1168 KB	Output is correct
20	Correct	89 ms	1168 KB	Output is correct
21	Correct	377 ms	1168 KB	Output is correct
22	Correct	420 ms	1168 KB	Output is correct
23	Correct	182 ms	1204 KB	Output is correct
24	Correct	710 ms	1208 KB	Output is correct
25	Correct	874 ms	1244 KB	Output is correct
26	Correct	836 ms	1244 KB	Output is correct
27	Correct	960 ms	1252 KB	Output is correct
28	Correct	933 ms	1256 KB	Output is correct
29	Correct	833 ms	1256 KB	Output is correct
30	Correct	762 ms	1264 KB	Output is correct
31	Correct	815 ms	1268 KB	Output is correct
32	Correct	845 ms	1268 KB	Output is correct
33	Correct	758 ms	1268 KB	Output is correct
34	Correct	785 ms	1280 KB	Output is correct
35	Correct	753 ms	1284 KB	Output is correct
36	Correct	792 ms	1292 KB	Output is correct
37	Execution timed out	1061 ms	1292 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	760 KB	Output is correct
2	Correct	7 ms	760 KB	Output is correct
3	Correct	4 ms	864 KB	Output is correct
4	Correct	5 ms	920 KB	Output is correct
5	Correct	15 ms	952 KB	Output is correct
6	Correct	12 ms	952 KB	Output is correct
7	Correct	9 ms	952 KB	Output is correct
8	Correct	14 ms	952 KB	Output is correct
9	Correct	10 ms	1020 KB	Output is correct
10	Correct	74 ms	1020 KB	Output is correct
11	Correct	82 ms	1020 KB	Output is correct
12	Correct	89 ms	1032 KB	Output is correct
13	Correct	54 ms	1032 KB	Output is correct
14	Correct	60 ms	1168 KB	Output is correct
15	Correct	63 ms	1168 KB	Output is correct
16	Correct	84 ms	1168 KB	Output is correct
17	Correct	27 ms	1168 KB	Output is correct
18	Correct	61 ms	1168 KB	Output is correct
19	Correct	60 ms	1168 KB	Output is correct
20	Correct	89 ms	1168 KB	Output is correct
21	Correct	377 ms	1168 KB	Output is correct
22	Correct	420 ms	1168 KB	Output is correct
23	Correct	182 ms	1204 KB	Output is correct
24	Correct	710 ms	1208 KB	Output is correct
25	Correct	874 ms	1244 KB	Output is correct
26	Correct	836 ms	1244 KB	Output is correct
27	Correct	960 ms	1252 KB	Output is correct
28	Correct	933 ms	1256 KB	Output is correct
29	Correct	833 ms	1256 KB	Output is correct
30	Correct	762 ms	1264 KB	Output is correct
31	Correct	815 ms	1268 KB	Output is correct
32	Correct	845 ms	1268 KB	Output is correct
33	Correct	758 ms	1268 KB	Output is correct
34	Correct	785 ms	1280 KB	Output is correct
35	Correct	753 ms	1284 KB	Output is correct
36	Correct	792 ms	1292 KB	Output is correct
37	Execution timed out	1061 ms	1292 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	760 KB	Output is correct
2	Correct	7 ms	760 KB	Output is correct
3	Correct	4 ms	864 KB	Output is correct
4	Correct	5 ms	920 KB	Output is correct
5	Correct	15 ms	952 KB	Output is correct
6	Correct	12 ms	952 KB	Output is correct
7	Correct	9 ms	952 KB	Output is correct
8	Correct	14 ms	952 KB	Output is correct
9	Correct	10 ms	1020 KB	Output is correct
10	Correct	74 ms	1020 KB	Output is correct
11	Correct	82 ms	1020 KB	Output is correct
12	Correct	89 ms	1032 KB	Output is correct
13	Correct	54 ms	1032 KB	Output is correct
14	Correct	60 ms	1168 KB	Output is correct
15	Correct	63 ms	1168 KB	Output is correct
16	Correct	84 ms	1168 KB	Output is correct
17	Correct	27 ms	1168 KB	Output is correct
18	Correct	61 ms	1168 KB	Output is correct
19	Correct	60 ms	1168 KB	Output is correct
20	Correct	89 ms	1168 KB	Output is correct
21	Correct	377 ms	1168 KB	Output is correct
22	Correct	420 ms	1168 KB	Output is correct
23	Correct	182 ms	1204 KB	Output is correct
24	Correct	710 ms	1208 KB	Output is correct
25	Correct	874 ms	1244 KB	Output is correct
26	Correct	836 ms	1244 KB	Output is correct
27	Correct	960 ms	1252 KB	Output is correct
28	Correct	933 ms	1256 KB	Output is correct
29	Correct	833 ms	1256 KB	Output is correct
30	Correct	762 ms	1264 KB	Output is correct
31	Correct	815 ms	1268 KB	Output is correct
32	Correct	845 ms	1268 KB	Output is correct
33	Correct	758 ms	1268 KB	Output is correct
34	Correct	785 ms	1280 KB	Output is correct
35	Correct	753 ms	1284 KB	Output is correct
36	Correct	792 ms	1292 KB	Output is correct
37	Execution timed out	1061 ms	1292 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #58453

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 15.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
15.0 / 15.0

Subtask #4
0 / 16.0

Subtask #5
0 / 21.0

Subtask #6
0 / 35.0