oj.uz

Submission #873140

# Submission time Handle Problem Language Result Execution time Memory
873140 2023-11-14T14:05:12 Z svorogaze Council (JOI23_council) C++17
6 / 100
 452 ms 33104 KB 
/*
Disgrace. Humiliation. Unseemly and unwelcome at the feet of The Council.
Their eyes ablaze with bitter resentment, glaring through Gabriel’s wounds of body and soul,
bore outward for all to see.

"Has this one abandoned the way of our Creator?"
"It is unworthy of its Holy Light."
"The Father's Light is indomitable."
"This one only sees fit to squander it."

Their words resonated in Gabriel's limbs, coursing through as lightning upon wire,
a searing hiss that would strike lessers deaf and blind.
The Holy Light within him, an unstoppable storm of divine fury.
Insurmountable for mere objects.
This he knew.

"Holy Council, my devotion to our Creator is absolute.
I have never strayed from the will of the Father, but a machine-"

"You dare imply the might of the Father could be shaken by mere objects?"
"Impossible."
"Heresy."
"Unspeakable."
"Heresy."
"Heresy."
"Silence!"
"Your failure will not be tolerated. As punishment, the Father's Light shall be severed
from your body. You have 24 hours before the last of its embers die out."
"And you with them."
"Prove your loyalty."
"Unmake your mistakes."

As the Light was ripped from his being, Gabriel’s screams were silenced
in the hiss of gospel in praise of God.
A boiling anguish to which even the fires of hell could not compare.
Through the blaze of torment a single burning hatred was forged anew.

If the machines seek blood, he would give it freely; and with such fury, even metal will bleed.
*/

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, std::greater<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    indexed_set;
typedef tree<long long, null_type, greater_equal<>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define fastio \
    std::cin.tie(0), std::cout.tie(0), std::ios_base::sync_with_stdio(false)
#define rep(a, b, c, d) for (int a = b; a < c; a += d)
#define INF ((1ll << 50) - 1)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define x first
#define y second
#define ld long double
#define MAXN 201000
struct msk {
    int mask = 0, ind = -1;
};
msk mdp[(1ll << 20)][2];

bool big(msk m1, msk m2, int cm) {
    if (__builtin_popcount(m1.mask & cm) == __builtin_popcount(m2.mask & cm)) {
        return __builtin_popcount(m1.mask) > __builtin_popcount(m2.mask);
    }
    return __builtin_popcount(m1.mask & cm) > __builtin_popcount(m2.mask & cm);
}

signed main() {
    //fastio;
    int n, m;
    cin >> n >> m;
    vector<int> msks(n);
    vector<int> cnt(m, -(n / 2));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int x;
            cin >> x;
            x ^= 1;
            if (x) msks[i] += (1ll << j);
            if (!x) cnt[j]++;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if ((1ll << j) & msks[i]) {
                if (big({msks[i], i}, mdp[(1ll << j)][0], (1ll << j))) {
                    mdp[(1ll << j)][1] = mdp[(1ll << j)][0];
                    mdp[(1ll << j)][0] = {msks[i], i};
                } else if (big({msks[i], i}, mdp[(1ll << j)][1], (1ll << j))) {
                    mdp[(1ll << j)][1] = {msks[i], i};
                }
            }
        }
    }
    for (int mask = 0; mask < (1ll << m); ++mask) {
        if (__builtin_popcount(mask) <= 1) continue;
        for (int j = 0; j < m; ++j) {
            if (mask & (1ll << j)) {
                for (int k = 0; k < 2; ++k) {
                    if (big(mdp[mask - (1ll << j)][k], mdp[mask][0], mask)) {
                        mdp[mask][1] = mdp[mask][0];
                        mdp[mask][0] = mdp[mask - (1ll << j)][k];
                    } else if (big(mdp[mask - (1ll << j)][k], mdp[mask][1], mask) && mdp[mask][0].ind != mdp[mask - (1ll << j)][k].ind) {
                        mdp[mask][1] = mdp[mask - (1ll << j)][k];
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        int res = 0;
        int cm = 0;
        for (int j = 0; j < m; ++j) {
            if ((msks[i] & (1ll << j))) {
                //
            } else {
                cnt[j]--;
            }
            if (cnt[j] != 0) {
                if (cnt[j] > 0) res++;
            } else {
                cm += (1ll << j);
            }
        }
        if (mdp[cm][0].ind != i) {
            res += __builtin_popcount(mdp[cm][0].mask & cm);
        } else {
            if (mdp[cm][1].ind == i) exit(100);
            res += __builtin_popcount(mdp[cm][1].mask & cm);
        }
        cout << res << '\n';
        for (int j = 0; j < m; ++j) {
            if ((msks[i] & (1ll << j))) {
                //
            } else {
                cnt[j]++;
            }
        }
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 371 ms 33104 KB Output is correct
6 Correct 381 ms 708 KB Output is correct
7 Correct 325 ms 33052 KB Output is correct
8 Incorrect 367 ms 33028 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 371 ms 33104 KB Output is correct
6 Correct 381 ms 708 KB Output is correct
7 Correct 325 ms 33052 KB Output is correct
8 Incorrect 367 ms 33028 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 102 ms 4424 KB Output is correct
3 Correct 95 ms 4432 KB Output is correct
4 Correct 56 ms 3908 KB Output is correct
5 Correct 95 ms 4556 KB Output is correct
6 Correct 59 ms 3924 KB Output is correct
7 Correct 96 ms 4424 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 102 ms 4424 KB Output is correct
3 Correct 95 ms 4432 KB Output is correct
4 Correct 56 ms 3908 KB Output is correct
5 Correct 95 ms 4556 KB Output is correct
6 Correct 59 ms 3924 KB Output is correct
7 Correct 96 ms 4424 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 452 ms 9164 KB Output is correct
21 Correct 359 ms 8528 KB Output is correct
22 Incorrect 375 ms 8780 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 102 ms 4424 KB Output is correct
3 Correct 95 ms 4432 KB Output is correct
4 Correct 56 ms 3908 KB Output is correct
5 Correct 95 ms 4556 KB Output is correct
6 Correct 59 ms 3924 KB Output is correct
7 Correct 96 ms 4424 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 452 ms 9164 KB Output is correct
21 Correct 359 ms 8528 KB Output is correct
22 Incorrect 375 ms 8780 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 102 ms 4424 KB Output is correct
3 Correct 95 ms 4432 KB Output is correct
4 Correct 56 ms 3908 KB Output is correct
5 Correct 95 ms 4556 KB Output is correct
6 Correct 59 ms 3924 KB Output is correct
7 Correct 96 ms 4424 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 452 ms 9164 KB Output is correct
21 Correct 359 ms 8528 KB Output is correct
22 Incorrect 375 ms 8780 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 371 ms 33104 KB Output is correct
6 Correct 381 ms 708 KB Output is correct
7 Correct 325 ms 33052 KB Output is correct
8 Incorrect 367 ms 33028 KB Output isn't correct
9 Halted 0 ms 0 KB -