답안 #51307 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51307	2018-06-17T12:39:51 Z	Nicksechko	Bootfall (IZhO17_bootfall)	C++11	100 / 100	980 ms	4276 KB

bootfall

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <queue>
#include <unordered_map>
//#include <unordered_set>
#include <iomanip>
#include <stack>
#include <ctime>
#include <cassert>
#include <cmath>

#define y1 ups
#define left lll
#define right rrr
#define next nnn
//#define find fff

typedef unsigned long long ull;

using namespace std;

//mt19937_64 twister(chrono::steady_clock().now().time_since_epoch().count());
mt19937_64 twister(8888);

long long rnd(long long l, long long r)
{
    uniform_int_distribution<long long> dis(l, r);
    return dis(twister);
}

const int mod = (int)1e9 + 7;
//const int mod[2] = {(int)1e9 + 7, (int)1e9 + 9};
//const int st[2] = {887, 8887};'
const int maxn = 588;
const int inf = 1e4 + 88;
const int logn = 22;
const int maxa = 500*500 + 88;
const int block = 775;
const long long infll = 1e18 + 88;
const char sgl[5] = {'a', 'e', 'i', 'o', 'u'};
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int knightx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int knighty[] = {-1, 1, -2, 2, -2, 2, -1, 1};
const int kingx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int kingy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const char sep = 'a' - 1;
const double eps = 1e-9;
const int maxn1 = 1e3 + 88;

//#define int long long

int a[588];
int ans[maxa], dp[maxa];
int all_sum;
vector<int> v;

int msum(int a, int b)
{
    return (a + b)%mod;
}

void add(int x)
{
    all_sum += x;
    for (int i = maxa - x - 1; i >= 0; i--)
        dp[i + x] = msum(dp[i + x], dp[i]);
}

void del(int x)
{
    all_sum -= x;
    for (int i = 0; i + x < maxa; i++)
        dp[i + x] = msum(dp[i + x], mod - dp[i]);
}

void solve()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    ifstream cin("input.txt");
//    ofstream cout("output.txt");
//    ifstream cin("bootfall.in");
//    ofstream cout("bootfall.out");
    int n, i, j;
    cin >> n;
    dp[0] = 1;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
        add(a[i]);
    }
    if ((all_sum&1) || dp[all_sum >> 1] == 0)
    {
        cout << 0;
        return;
    }
    for (i = 1; i < maxa; i++)
        ans[i] = true;
    for (i = 0; i < n; i++)
    {
        del(a[i]);
        for (j = 1; j < maxa; j++)
            if (((all_sum + j)&1) || dp[(all_sum + j) >> 1] == 0)
                ans[j] = false;
        add(a[i]);
    }
    for (i = 0; i < maxa; i++)
        if (ans[i])
            v.push_back(i);
    cout << v.size() << "\n";
    for (i = 0; i < v.size(); i++)
        cout << v[i] << " ";
}

//#undef int

int main()
{
//    srand(time(0));
//    srand(8);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    ifstream cin("input.txt");
//    ofstream cout("output.txt");
//    ifstream cin("output.txt");
//    ifstream fin("12.out");
//    int a, b, i = 0;
//    while (cin >> a)
//    {
//        fin >> b;
//        if (a != b)
//        {
//            cout << i << " " << a << " " << b;
//            return 0;
//        }
//        i++;
//    }
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    freopen("f.in", "r", stdin);
//    freopen("f.out", "w", stdout);
//    int t = 10000;
//    while (t--)
//    {
//        if (t == 9947)
//            t = 9947;
//        gen();
//        cout << t << endl;
//        brut();
//        if (!solve())
//        {
//            cout << "kek";
//            return 0;
//        }
//    }
    solve();
    return 0;
}

Compilation message

bootfall.cpp: In function 'void solve()':
bootfall.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < v.size(); i++)
                 ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	2296 KB	Output is correct
2	Correct	16 ms	2376 KB	Output is correct
3	Correct	5 ms	2376 KB	Output is correct
4	Correct	12 ms	2384 KB	Output is correct
5	Correct	25 ms	2400 KB	Output is correct
6	Correct	18 ms	2480 KB	Output is correct
7	Correct	15 ms	2480 KB	Output is correct
8	Correct	25 ms	2480 KB	Output is correct
9	Correct	22 ms	2516 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	2296 KB	Output is correct
2	Correct	16 ms	2376 KB	Output is correct
3	Correct	5 ms	2376 KB	Output is correct
4	Correct	12 ms	2384 KB	Output is correct
5	Correct	25 ms	2400 KB	Output is correct
6	Correct	18 ms	2480 KB	Output is correct
7	Correct	15 ms	2480 KB	Output is correct
8	Correct	25 ms	2480 KB	Output is correct
9	Correct	22 ms	2516 KB	Output is correct
10	Correct	63 ms	2576 KB	Output is correct
11	Correct	65 ms	2664 KB	Output is correct
12	Correct	57 ms	2664 KB	Output is correct
13	Correct	53 ms	2664 KB	Output is correct
14	Correct	55 ms	2664 KB	Output is correct
15	Correct	57 ms	2664 KB	Output is correct
16	Correct	76 ms	2664 KB	Output is correct
17	Correct	36 ms	2664 KB	Output is correct
18	Correct	48 ms	2664 KB	Output is correct
19	Correct	52 ms	2664 KB	Output is correct
20	Correct	56 ms	2664 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	2296 KB	Output is correct
2	Correct	16 ms	2376 KB	Output is correct
3	Correct	5 ms	2376 KB	Output is correct
4	Correct	12 ms	2384 KB	Output is correct
5	Correct	25 ms	2400 KB	Output is correct
6	Correct	18 ms	2480 KB	Output is correct
7	Correct	15 ms	2480 KB	Output is correct
8	Correct	25 ms	2480 KB	Output is correct
9	Correct	22 ms	2516 KB	Output is correct
10	Correct	63 ms	2576 KB	Output is correct
11	Correct	65 ms	2664 KB	Output is correct
12	Correct	57 ms	2664 KB	Output is correct
13	Correct	53 ms	2664 KB	Output is correct
14	Correct	55 ms	2664 KB	Output is correct
15	Correct	57 ms	2664 KB	Output is correct
16	Correct	76 ms	2664 KB	Output is correct
17	Correct	36 ms	2664 KB	Output is correct
18	Correct	48 ms	2664 KB	Output is correct
19	Correct	52 ms	2664 KB	Output is correct
20	Correct	56 ms	2664 KB	Output is correct
21	Correct	123 ms	2664 KB	Output is correct
22	Correct	142 ms	2664 KB	Output is correct
23	Correct	94 ms	2664 KB	Output is correct
24	Correct	185 ms	2664 KB	Output is correct
25	Correct	181 ms	2664 KB	Output is correct
26	Correct	181 ms	2664 KB	Output is correct
27	Correct	203 ms	2664 KB	Output is correct
28	Correct	197 ms	2664 KB	Output is correct
29	Correct	175 ms	2664 KB	Output is correct
30	Correct	177 ms	2664 KB	Output is correct
31	Correct	175 ms	2664 KB	Output is correct
32	Correct	190 ms	2664 KB	Output is correct
33	Correct	191 ms	2664 KB	Output is correct
34	Correct	178 ms	2732 KB	Output is correct
35	Correct	184 ms	2732 KB	Output is correct
36	Correct	196 ms	2732 KB	Output is correct

Subtask #4
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	2296 KB	Output is correct
2	Correct	16 ms	2376 KB	Output is correct
3	Correct	5 ms	2376 KB	Output is correct
4	Correct	12 ms	2384 KB	Output is correct
5	Correct	25 ms	2400 KB	Output is correct
6	Correct	18 ms	2480 KB	Output is correct
7	Correct	15 ms	2480 KB	Output is correct
8	Correct	25 ms	2480 KB	Output is correct
9	Correct	22 ms	2516 KB	Output is correct
10	Correct	63 ms	2576 KB	Output is correct
11	Correct	65 ms	2664 KB	Output is correct
12	Correct	57 ms	2664 KB	Output is correct
13	Correct	53 ms	2664 KB	Output is correct
14	Correct	55 ms	2664 KB	Output is correct
15	Correct	57 ms	2664 KB	Output is correct
16	Correct	76 ms	2664 KB	Output is correct
17	Correct	36 ms	2664 KB	Output is correct
18	Correct	48 ms	2664 KB	Output is correct
19	Correct	52 ms	2664 KB	Output is correct
20	Correct	56 ms	2664 KB	Output is correct
21	Correct	123 ms	2664 KB	Output is correct
22	Correct	142 ms	2664 KB	Output is correct
23	Correct	94 ms	2664 KB	Output is correct
24	Correct	185 ms	2664 KB	Output is correct
25	Correct	181 ms	2664 KB	Output is correct
26	Correct	181 ms	2664 KB	Output is correct
27	Correct	203 ms	2664 KB	Output is correct
28	Correct	197 ms	2664 KB	Output is correct
29	Correct	175 ms	2664 KB	Output is correct
30	Correct	177 ms	2664 KB	Output is correct
31	Correct	175 ms	2664 KB	Output is correct
32	Correct	190 ms	2664 KB	Output is correct
33	Correct	191 ms	2664 KB	Output is correct
34	Correct	178 ms	2732 KB	Output is correct
35	Correct	184 ms	2732 KB	Output is correct
36	Correct	196 ms	2732 KB	Output is correct
37	Correct	345 ms	2860 KB	Output is correct
38	Correct	368 ms	2860 KB	Output is correct
39	Correct	446 ms	2860 KB	Output is correct
40	Correct	507 ms	2860 KB	Output is correct
41	Correct	543 ms	2860 KB	Output is correct
42	Correct	488 ms	2860 KB	Output is correct
43	Correct	452 ms	3148 KB	Output is correct
44	Correct	436 ms	3148 KB	Output is correct
45	Correct	442 ms	3148 KB	Output is correct
46	Correct	481 ms	3148 KB	Output is correct
47	Correct	469 ms	3148 KB	Output is correct
48	Correct	483 ms	3148 KB	Output is correct
49	Correct	538 ms	3148 KB	Output is correct
50	Correct	477 ms	3148 KB	Output is correct
51	Correct	156 ms	3148 KB	Output is correct
52	Correct	536 ms	3148 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	2296 KB	Output is correct
2	Correct	16 ms	2376 KB	Output is correct
3	Correct	5 ms	2376 KB	Output is correct
4	Correct	12 ms	2384 KB	Output is correct
5	Correct	25 ms	2400 KB	Output is correct
6	Correct	18 ms	2480 KB	Output is correct
7	Correct	15 ms	2480 KB	Output is correct
8	Correct	25 ms	2480 KB	Output is correct
9	Correct	22 ms	2516 KB	Output is correct
10	Correct	63 ms	2576 KB	Output is correct
11	Correct	65 ms	2664 KB	Output is correct
12	Correct	57 ms	2664 KB	Output is correct
13	Correct	53 ms	2664 KB	Output is correct
14	Correct	55 ms	2664 KB	Output is correct
15	Correct	57 ms	2664 KB	Output is correct
16	Correct	76 ms	2664 KB	Output is correct
17	Correct	36 ms	2664 KB	Output is correct
18	Correct	48 ms	2664 KB	Output is correct
19	Correct	52 ms	2664 KB	Output is correct
20	Correct	56 ms	2664 KB	Output is correct
21	Correct	123 ms	2664 KB	Output is correct
22	Correct	142 ms	2664 KB	Output is correct
23	Correct	94 ms	2664 KB	Output is correct
24	Correct	185 ms	2664 KB	Output is correct
25	Correct	181 ms	2664 KB	Output is correct
26	Correct	181 ms	2664 KB	Output is correct
27	Correct	203 ms	2664 KB	Output is correct
28	Correct	197 ms	2664 KB	Output is correct
29	Correct	175 ms	2664 KB	Output is correct
30	Correct	177 ms	2664 KB	Output is correct
31	Correct	175 ms	2664 KB	Output is correct
32	Correct	190 ms	2664 KB	Output is correct
33	Correct	191 ms	2664 KB	Output is correct
34	Correct	178 ms	2732 KB	Output is correct
35	Correct	184 ms	2732 KB	Output is correct
36	Correct	196 ms	2732 KB	Output is correct
37	Correct	345 ms	2860 KB	Output is correct
38	Correct	368 ms	2860 KB	Output is correct
39	Correct	446 ms	2860 KB	Output is correct
40	Correct	507 ms	2860 KB	Output is correct
41	Correct	543 ms	2860 KB	Output is correct
42	Correct	488 ms	2860 KB	Output is correct
43	Correct	452 ms	3148 KB	Output is correct
44	Correct	436 ms	3148 KB	Output is correct
45	Correct	442 ms	3148 KB	Output is correct
46	Correct	481 ms	3148 KB	Output is correct
47	Correct	469 ms	3148 KB	Output is correct
48	Correct	483 ms	3148 KB	Output is correct
49	Correct	538 ms	3148 KB	Output is correct
50	Correct	477 ms	3148 KB	Output is correct
51	Correct	156 ms	3148 KB	Output is correct
52	Correct	536 ms	3148 KB	Output is correct
53	Correct	562 ms	3148 KB	Output is correct
54	Correct	643 ms	3148 KB	Output is correct
55	Correct	629 ms	3260 KB	Output is correct
56	Correct	577 ms	3260 KB	Output is correct
57	Correct	634 ms	3260 KB	Output is correct
58	Correct	619 ms	3260 KB	Output is correct
59	Correct	649 ms	3260 KB	Output is correct
60	Correct	189 ms	3260 KB	Output is correct
61	Correct	629 ms	3272 KB	Output is correct
62	Correct	570 ms	3300 KB	Output is correct
63	Correct	669 ms	3464 KB	Output is correct
64	Correct	691 ms	3464 KB	Output is correct
65	Correct	616 ms	3464 KB	Output is correct
66	Correct	576 ms	3464 KB	Output is correct

Subtask #6
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	2296 KB	Output is correct
2	Correct	16 ms	2376 KB	Output is correct
3	Correct	5 ms	2376 KB	Output is correct
4	Correct	12 ms	2384 KB	Output is correct
5	Correct	25 ms	2400 KB	Output is correct
6	Correct	18 ms	2480 KB	Output is correct
7	Correct	15 ms	2480 KB	Output is correct
8	Correct	25 ms	2480 KB	Output is correct
9	Correct	22 ms	2516 KB	Output is correct
10	Correct	63 ms	2576 KB	Output is correct
11	Correct	65 ms	2664 KB	Output is correct
12	Correct	57 ms	2664 KB	Output is correct
13	Correct	53 ms	2664 KB	Output is correct
14	Correct	55 ms	2664 KB	Output is correct
15	Correct	57 ms	2664 KB	Output is correct
16	Correct	76 ms	2664 KB	Output is correct
17	Correct	36 ms	2664 KB	Output is correct
18	Correct	48 ms	2664 KB	Output is correct
19	Correct	52 ms	2664 KB	Output is correct
20	Correct	56 ms	2664 KB	Output is correct
21	Correct	123 ms	2664 KB	Output is correct
22	Correct	142 ms	2664 KB	Output is correct
23	Correct	94 ms	2664 KB	Output is correct
24	Correct	185 ms	2664 KB	Output is correct
25	Correct	181 ms	2664 KB	Output is correct
26	Correct	181 ms	2664 KB	Output is correct
27	Correct	203 ms	2664 KB	Output is correct
28	Correct	197 ms	2664 KB	Output is correct
29	Correct	175 ms	2664 KB	Output is correct
30	Correct	177 ms	2664 KB	Output is correct
31	Correct	175 ms	2664 KB	Output is correct
32	Correct	190 ms	2664 KB	Output is correct
33	Correct	191 ms	2664 KB	Output is correct
34	Correct	178 ms	2732 KB	Output is correct
35	Correct	184 ms	2732 KB	Output is correct
36	Correct	196 ms	2732 KB	Output is correct
37	Correct	345 ms	2860 KB	Output is correct
38	Correct	368 ms	2860 KB	Output is correct
39	Correct	446 ms	2860 KB	Output is correct
40	Correct	507 ms	2860 KB	Output is correct
41	Correct	543 ms	2860 KB	Output is correct
42	Correct	488 ms	2860 KB	Output is correct
43	Correct	452 ms	3148 KB	Output is correct
44	Correct	436 ms	3148 KB	Output is correct
45	Correct	442 ms	3148 KB	Output is correct
46	Correct	481 ms	3148 KB	Output is correct
47	Correct	469 ms	3148 KB	Output is correct
48	Correct	483 ms	3148 KB	Output is correct
49	Correct	538 ms	3148 KB	Output is correct
50	Correct	477 ms	3148 KB	Output is correct
51	Correct	156 ms	3148 KB	Output is correct
52	Correct	536 ms	3148 KB	Output is correct
53	Correct	562 ms	3148 KB	Output is correct
54	Correct	643 ms	3148 KB	Output is correct
55	Correct	629 ms	3260 KB	Output is correct
56	Correct	577 ms	3260 KB	Output is correct
57	Correct	634 ms	3260 KB	Output is correct
58	Correct	619 ms	3260 KB	Output is correct
59	Correct	649 ms	3260 KB	Output is correct
60	Correct	189 ms	3260 KB	Output is correct
61	Correct	629 ms	3272 KB	Output is correct
62	Correct	570 ms	3300 KB	Output is correct
63	Correct	669 ms	3464 KB	Output is correct
64	Correct	691 ms	3464 KB	Output is correct
65	Correct	616 ms	3464 KB	Output is correct
66	Correct	576 ms	3464 KB	Output is correct
67	Correct	728 ms	3464 KB	Output is correct
68	Correct	267 ms	3464 KB	Output is correct
69	Correct	974 ms	3900 KB	Output is correct
70	Correct	911 ms	3900 KB	Output is correct
71	Correct	942 ms	3900 KB	Output is correct
72	Correct	980 ms	3900 KB	Output is correct
73	Correct	895 ms	3900 KB	Output is correct
74	Correct	910 ms	4048 KB	Output is correct
75	Correct	957 ms	4048 KB	Output is correct
76	Correct	856 ms	4048 KB	Output is correct
77	Correct	897 ms	4276 KB	Output is correct

답안 #51307

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 15.0 / 15.0

Subtask #4 16.0 / 16.0

Subtask #5 21.0 / 21.0

Subtask #6 35.0 / 35.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
15.0 / 15.0

Subtask #4
16.0 / 16.0

Subtask #5
21.0 / 21.0

Subtask #6
35.0 / 35.0