oj.uz

Submission #675654

# Submission time Handle Problem Language Result Execution time Memory
675654 2022-12-27T15:49:52 Z LucaIlie Bootfall (IZhO17_bootfall) C++17
13 / 100
 1000 ms 4192 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxN = 270;
const int maxS = 270 * 270;

using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> & a, bool invert) {
    int n = a.size();
    if (n == 1)
        return;

    vector<cd> a0(n / 2), a1(n / 2);
    for (int i = 0; 2 * i < n; i++) {
        a0[i] = a[2*i];
        a1[i] = a[2*i+1];
    }
    fft(a0, invert);
    fft(a1, invert);

    double ang = 2 * PI / n * (invert ? -1 : 1);
    cd w(1), wn(cos(ang), sin(ang));
    for (int i = 0; 2 * i < n; i++) {
        a[i] = a0[i] + w * a1[i];
        a[i + n/2] = a0[i] - w * a1[i];
        if (invert) {
            a[i] /= 2;
            a[i + n/2] /= 2;
        }
        w *= wn;
    }
}

vector<int> multiply(vector<int> const& a, vector<int> const& b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size())
        n <<= 1;
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++)
        fa[i] *= fb[i];
    fft(fa, true);

    vector<int> result(n);
    for (int i = 0; i < n; i++)
        result[i] = round(fa[i].real());
    return result;
}

int v[maxN + 1];
bitset<maxS + 1> pos1n[maxN + 1], posn1[maxN + 2];
bitset<maxS + 1> pos, tim, timTemp;

int main() {
    int n, s = 0;

    cin >> n;
    for ( int i = 1; i <= n; i++ )
        cin >> v[i], s += v[i];

    pos1n[0][0] = true;
    for ( int i = 1; i <= n; i++ )
        pos1n[i] = (pos1n[i - 1] | (pos1n[i - 1] << v[i]));
    posn1[n + 1][0] = true;
    for ( int i = n; i >= 1; i-- )
        posn1[i] = (posn1[i + 1] | (posn1[i + 1] << v[i]));

    if ( s % 2 != 0 || !pos1n[n][s / 2] ) {
        cout << 0;
        return 0;
    }

    for ( int i = 0; i <= s; i++ )
        tim[i] = true;
    for ( int r = 1; r <= n; r++ ) {
        vector<int> a, b;
        for ( int i = 0; i <= s; i++ ) {
            a.push_back( pos1n[r - 1][i] );
            b.push_back( posn1[r + 1][i] );
        }

        vector<int> pos = multiply( a, b );

        timTemp.reset();
        for ( int i = 0; i <= s; i++ ) {
            if ( pos[i] )
                timTemp[abs( s - v[r] - i - i )] = true;
        }
        tim &= timTemp;
    }

    tim[0] = false;
    cout << tim.count() << "\n";
    for ( int i = 0; i <= s; i++ ) {
        if ( tim[i] )
            cout << i << " ";
    }

    return 0;
}

Compilation message

bootfall.cpp: In function 'std::vector<int> multiply(const std::vector<int>&, const std::vector<int>&)':
bootfall.cpp:40:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     while (n < a.size() + b.size())
      |            ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 9 ms 696 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 24 ms 956 KB Output is correct
9 Correct 8 ms 668 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 9 ms 696 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 24 ms 956 KB Output is correct
9 Correct 8 ms 668 KB Output is correct
10 Correct 24 ms 1020 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 12 ms 964 KB Output is correct
13 Correct 7 ms 860 KB Output is correct
14 Correct 12 ms 928 KB Output is correct
15 Correct 9 ms 884 KB Output is correct
16 Correct 6 ms 932 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 4 ms 724 KB Output is correct
19 Correct 5 ms 852 KB Output is correct
20 Correct 23 ms 1024 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 9 ms 696 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 24 ms 956 KB Output is correct
9 Correct 8 ms 668 KB Output is correct
10 Correct 24 ms 1020 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 12 ms 964 KB Output is correct
13 Correct 7 ms 860 KB Output is correct
14 Correct 12 ms 928 KB Output is correct
15 Correct 9 ms 884 KB Output is correct
16 Correct 6 ms 932 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 4 ms 724 KB Output is correct
19 Correct 5 ms 852 KB Output is correct
20 Correct 23 ms 1024 KB Output is correct
21 Correct 207 ms 2052 KB Output is correct
22 Correct 243 ms 2252 KB Output is correct
23 Correct 159 ms 1788 KB Output is correct
24 Correct 632 ms 3148 KB Output is correct
25 Execution timed out 1072 ms 4192 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 9 ms 696 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 24 ms 956 KB Output is correct
9 Correct 8 ms 668 KB Output is correct
10 Correct 24 ms 1020 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 12 ms 964 KB Output is correct
13 Correct 7 ms 860 KB Output is correct
14 Correct 12 ms 928 KB Output is correct
15 Correct 9 ms 884 KB Output is correct
16 Correct 6 ms 932 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 4 ms 724 KB Output is correct
19 Correct 5 ms 852 KB Output is correct
20 Correct 23 ms 1024 KB Output is correct
21 Correct 207 ms 2052 KB Output is correct
22 Correct 243 ms 2252 KB Output is correct
23 Correct 159 ms 1788 KB Output is correct
24 Correct 632 ms 3148 KB Output is correct
25 Execution timed out 1072 ms 4192 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 9 ms 696 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 24 ms 956 KB Output is correct
9 Correct 8 ms 668 KB Output is correct
10 Correct 24 ms 1020 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 12 ms 964 KB Output is correct
13 Correct 7 ms 860 KB Output is correct
14 Correct 12 ms 928 KB Output is correct
15 Correct 9 ms 884 KB Output is correct
16 Correct 6 ms 932 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 4 ms 724 KB Output is correct
19 Correct 5 ms 852 KB Output is correct
20 Correct 23 ms 1024 KB Output is correct
21 Correct 207 ms 2052 KB Output is correct
22 Correct 243 ms 2252 KB Output is correct
23 Correct 159 ms 1788 KB Output is correct
24 Correct 632 ms 3148 KB Output is correct
25 Execution timed out 1072 ms 4192 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 9 ms 696 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 24 ms 956 KB Output is correct
9 Correct 8 ms 668 KB Output is correct
10 Correct 24 ms 1020 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 12 ms 964 KB Output is correct
13 Correct 7 ms 860 KB Output is correct
14 Correct 12 ms 928 KB Output is correct
15 Correct 9 ms 884 KB Output is correct
16 Correct 6 ms 932 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 4 ms 724 KB Output is correct
19 Correct 5 ms 852 KB Output is correct
20 Correct 23 ms 1024 KB Output is correct
21 Correct 207 ms 2052 KB Output is correct
22 Correct 243 ms 2252 KB Output is correct
23 Correct 159 ms 1788 KB Output is correct
24 Correct 632 ms 3148 KB Output is correct
25 Execution timed out 1072 ms 4192 KB Time limit exceeded
26 Halted 0 ms 0 KB -