oj.uz

Submission #843941

# Submission time Handle Problem Language Result Execution time Memory
843941 2023-09-04T17:46:48 Z biximo Council (JOI23_council) C++17
0 / 100
 247 ms 179288 KB 
#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
int n, m, te, bits[20] = {0};
p dp[1048576][21];
bool poss[1048576] = {0};
vector<int> council, cnts, dpCouncils;
int main() {
    for(auto&i: dp) for(auto&j: i) j = {0, 0};
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    council.resize(n);
    for(auto&i: council) {
        i = 0;
        for(int j = 0; j < m; j ++) {
            cin >> te;
            if(te) {
                i += (1 << j);
                bits[j] ++;
            }
        }
        poss[((1 << m) - 1) & (~i)] = 1;
    }
    for(auto&i: council) {
        int ni = 0;
        int cnt = 0;
        for(int j = 0; j < m; j ++) {
            int cb = bits[j];
            if(i & (1 << j)) cb --;
            if(cb - 1 >= (n) / 2) {
                cnt ++;
            }
            else if(cb >= (n) / 2) {
                ni += (1 << j);
            }
        }
        dpCouncils.push_back(ni);
        cnts.push_back(cnt);
    }
    for(int i = 0; i < (1 << m); i ++) {
        dp[i][0] = {(poss[i] ? __builtin_popcount(i) : 0), 0};
        if((poss[i] ? __builtin_popcount(i) : 0) == 10) {
//            cout << i << "\n";
        }
    }
    for(int j = 1; j <= m; j ++) {
        for(int i = 0; i < (1 << m); i ++) {
            int max1 = dp[i][j - 1].first;
            int max2 = dp[i][j - 1].second;
            auto c = ((i & (1 << (j - 1))) ? dp[i - (1 << (j - 1))][j - 1] : pair<int, int>(dp[i + (1 << (j - 1))][j - 1].first - 1, dp[i + (1 << (j - 1))][j - 1].second - 1));
            if(max1 >= c.first) max2 = max(max2, c.first);
            else {
                max2 = max(max1, c.second);
                max1 = c.first;
            }
            dp[i][j] = {max1, max2};
        }
    }
    for(int i = 0; i < n; i ++) {
        int maxV = 0;
        for(int j = 0; j < m; j ++) {
            int cb = bits[j];
            if(council[i] & (1 << j)) cb --;
            if(cb - 1 >= (n) / 2) {
            }
            else if(cb >= (n) / 2) {
                if(!(council[i] & (1 << j))) maxV ++;
            }
        }
//        cout << maxV << "\n";
//        cout << cnts[i] << "\n";
        cout << cnts[i] + ((maxV == dp[dpCouncils[i]][m].first) ? dp[dpCouncils[i]][m].second : dp[dpCouncils[i]][m].first) << "\n";
        assert(cnts[i] + (maxV == dp[dpCouncils[i]][m].first ? dp[dpCouncils[i]][m].second : dp[dpCouncils[i]][m].first) <= m);
//        cout << cnts[i] << "\n";
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 173652 KB Output is correct
2 Correct 30 ms 173652 KB Output is correct
3 Correct 31 ms 173448 KB Output is correct
4 Correct 30 ms 173588 KB Output is correct
5 Correct 225 ms 173652 KB Output is correct
6 Correct 225 ms 173652 KB Output is correct
7 Correct 218 ms 173660 KB Output is correct
8 Correct 234 ms 173908 KB Output is correct
9 Correct 244 ms 173652 KB Output is correct
10 Correct 238 ms 173496 KB Output is correct
11 Correct 237 ms 173672 KB Output is correct
12 Correct 247 ms 173660 KB Output is correct
13 Incorrect 31 ms 173660 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 173652 KB Output is correct
2 Correct 30 ms 173652 KB Output is correct
3 Correct 31 ms 173448 KB Output is correct
4 Correct 30 ms 173588 KB Output is correct
5 Correct 225 ms 173652 KB Output is correct
6 Correct 225 ms 173652 KB Output is correct
7 Correct 218 ms 173660 KB Output is correct
8 Correct 234 ms 173908 KB Output is correct
9 Correct 244 ms 173652 KB Output is correct
10 Correct 238 ms 173496 KB Output is correct
11 Correct 237 ms 173672 KB Output is correct
12 Correct 247 ms 173660 KB Output is correct
13 Incorrect 31 ms 173660 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 173524 KB Output is correct
2 Correct 73 ms 179188 KB Output is correct
3 Correct 69 ms 179288 KB Output is correct
4 Correct 67 ms 178612 KB Output is correct
5 Correct 76 ms 179196 KB Output is correct
6 Incorrect 68 ms 178624 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 173524 KB Output is correct
2 Correct 73 ms 179188 KB Output is correct
3 Correct 69 ms 179288 KB Output is correct
4 Correct 67 ms 178612 KB Output is correct
5 Correct 76 ms 179196 KB Output is correct
6 Incorrect 68 ms 178624 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 173524 KB Output is correct
2 Correct 73 ms 179188 KB Output is correct
3 Correct 69 ms 179288 KB Output is correct
4 Correct 67 ms 178612 KB Output is correct
5 Correct 76 ms 179196 KB Output is correct
6 Incorrect 68 ms 178624 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 173524 KB Output is correct
2 Correct 73 ms 179188 KB Output is correct
3 Correct 69 ms 179288 KB Output is correct
4 Correct 67 ms 178612 KB Output is correct
5 Correct 76 ms 179196 KB Output is correct
6 Incorrect 68 ms 178624 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 173652 KB Output is correct
2 Correct 30 ms 173652 KB Output is correct
3 Correct 31 ms 173448 KB Output is correct
4 Correct 30 ms 173588 KB Output is correct
5 Correct 225 ms 173652 KB Output is correct
6 Correct 225 ms 173652 KB Output is correct
7 Correct 218 ms 173660 KB Output is correct
8 Correct 234 ms 173908 KB Output is correct
9 Correct 244 ms 173652 KB Output is correct
10 Correct 238 ms 173496 KB Output is correct
11 Correct 237 ms 173672 KB Output is correct
12 Correct 247 ms 173660 KB Output is correct
13 Incorrect 31 ms 173660 KB Output isn't correct
14 Halted 0 ms 0 KB -