oj.uz

Submission #464872

# Submission time Handle Problem Language Result Execution time Memory
464872 2021-08-14T10:56:42 Z TeaTime Bootfall (IZhO17_bootfall) C++17
0 / 100
 15 ms 1520 KB 
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <bitset>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

#define int ll
const ll INF = 1e9, SZ = 510 * 510, SZ2 = 510;

ll n;
vector<ll> vec;
bitset<SZ> bts;
bitset<SZ> pref[SZ2], suf[SZ2], un[SZ2];

signed main() {
    fastInp;

    cin >> n;
    vec.resize(n);

    for (auto& c : vec) cin >> c;

    bts[0] = 1;
    ll sm = 0;

    pref[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        pref[i] = (pref[i - 1] | (pref[i - 1] << vec[i - 1]));
    }

    suf[n][0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = (suf[i + 1] | (suf[i + 1] << vec[i]));
    }

    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < SZ2; j++) {
            if (pref[i][j]) un[i] |= (suf[i + 1] << j);
        }
    }

    for (auto c : vec) {
        sm += c;
        bts |= (bts << c);
    }

    if (sm % 2) {
        cout << "0";
        return 0;
    }

    if (bts[sm / 2] != 1) {
        cout << "0";
        return 0;
    }

    vector<ll> ans;

    for (int i = 0; i < SZ; i++) {
        bool f = 1;
        for (int j = 0; j < n; j++) {
            ll cursm = sm - vec[j] + i;
            if (cursm % 2) {
                f = 0;
                break;
            }

            cursm /= 2;
            if (i > cursm) {
                f = 0;
                break;
            }

            if (un[j][cursm - i]) continue;

            f = 0;
            break;
        }

        if (f) ans.push_back(i);
    }

    cout << ans.size() << "\n";
    for (auto c : ans) cout << c << " ";
   
    return 0;
}

/*
3 4
RGWR
GRGG
RGWW

4 4
RGWR
GRRG
WGGW
WWWR

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 15 ms 1520 KB Output is correct
6 Correct 4 ms 1100 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Incorrect 9 ms 1492 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 15 ms 1520 KB Output is correct
6 Correct 4 ms 1100 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Incorrect 9 ms 1492 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 15 ms 1520 KB Output is correct
6 Correct 4 ms 1100 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Incorrect 9 ms 1492 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 15 ms 1520 KB Output is correct
6 Correct 4 ms 1100 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Incorrect 9 ms 1492 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 15 ms 1520 KB Output is correct
6 Correct 4 ms 1100 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Incorrect 9 ms 1492 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 15 ms 1520 KB Output is correct
6 Correct 4 ms 1100 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Incorrect 9 ms 1492 KB Output isn't correct
9 Halted 0 ms 0 KB -