oj.uz

Submission #796060

# Submission time Handle Problem Language Result Execution time Memory
796060 2023-07-28T05:37:50 Z 이동현(#10071) Council (JOI23_council) C++17
0 / 100
 810 ms 345124 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

const int NS = (int)3e5 + 4;
int n, m;
int a[NS], cnt[20], ans[NS];
int dp[21][1 << 20];
int id[21][1 << 20];
int dp2[21][1 << 20];
int id2[21][1 << 20];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            int x;
            cin >> x;
            a[i] |= (x << j);
            cnt[j] += x;
        }
    }

    vector<int> ncnt;
    for(int i = 0; i < n; ++i){
        int bt = 0, top = 0;
        for(int j = 0; j < m; ++j){
            if(cnt[j] >= n / 2 && cnt[j] < n / 2 + 2){
                if(!i){
                    ncnt.push_back(cnt[j]);
                }
                if(a[i] & (1 << j)){
                    bt |= 1 << top;
                }
                ++top;
            }
            if(cnt[j] >= n / 2 + 2){
                ans[i] += 1;
            }
        }
        a[i] = bt;
    }
    m = (int)ncnt.size();
    for(int i = 0; i < m; ++i){
        cnt[i] = ncnt[i];
    }

    for(int i = 0; i <= m; ++i){
        for(int j = 0; j < 1 << m; ++j){
            dp[i][j] = dp2[i][j] = 1000;
            id[i][j] = id2[i][j] = -1;
        }
    }
    for(int i = 0; i < n; ++i){
        dp[m][a[i]] = 0;
        id[m][a[i]] = i;
    }

    int all = (1 << m) - 1;
    for(int i = m - 1; i >= 0; --i){
        for(int j = 0; j < 1 << m; ++j){
            vector<pair<int, int>> srt(4);
            srt[0] = {dp[i + 1][j | (1 << i)] + !!(j & (1 << i)), id[i + 1][j | (1 << i)]};
            srt[1] = {dp2[i + 1][j | (1 << i)] + !!(j & (1 << i)), id2[i + 1][j | (1 << i)]};
            srt[2] = {dp[i + 1][j & (all - (1 << i))], id[i + 1][j & (all - (1 << i))]};
            srt[3] = {dp2[i + 1][j & (all - (1 << i))], id2[i + 1][j & (all - (1 << i))]};

            sort(srt.begin(), srt.end());
            dp[i][j] = srt[0].first, id[i][j] = srt[0].second;
            dp2[i][j] = srt[1 + (srt[0].second == srt[1].second)].first, id2[i][j] = srt[1 + (srt[0].second == srt[1].second)].second;
        }
    }

    for(int i = 0; i < n; ++i){
        int bt = 0;
        ans[i] += m;
        for(int j = 0; j < m; ++j){
            int v = cnt[j] - n / 2 - !!(a[i] & (1 << j));

            if(!v){
                bt |= (1 << j);
            }

            if((a[i] & (1 << j)) && cnt[j] == n / 2){
                --ans[i];
            }
        }

        // cout << a[i] << ' ' << bt << ' ' << dp[0][bt] << endl;

        // int mn = (int)1e9;
        // for(int j = 0; j < n; ++j){
        //     if(i != j){
        //         mn = min(mn, __builtin_popcount(bt & a[j]));
        //     }
        // }
        // ans[i] -= mn;
        ans[i] -= (id[0][bt] == i ? dp2[0][bt] : dp[0][bt]);

        cout << ans[i] << '\n';
    }
    
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 810 ms 345124 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 810 ms 345124 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 43 ms 3272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 43 ms 3272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 43 ms 3272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 43 ms 3272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 810 ms 345124 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -