oj.uz

Submission #768864

# Submission time Handle Problem Language Result Execution time Memory
768864 2023-06-28T19:37:36 Z danikoynov Council (JOI23_council) C++14
0 / 100
 4000 ms 8784 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 3e5 + 10, maxm = 21;
int n, m, imp[maxm], cnt[maxm];
bool a[maxn][maxm];
int dp[maxm][(1 << maxm)][2];
int val_mask[maxn], rev_mask[maxn];
void solve()
{

    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> a[i][j], cnt[j] += a[i][j];

    for (int mask = 0; mask < (1 << m); mask ++)
        for (int i = 0; i < m; i ++)
            dp[i][mask][0] = dp[i][mask][1] = -1;

            for (int i = 0; i < n; i ++)
                for (int j = 0; j < m; j ++)
                {
                    val_mask[i] = (val_mask[i] + (1 << j) * a[i][j]);
                    rev_mask[i] = (rev_mask[i] + (1 << j) * (1 - a[i][j]));
                }

    for (int i = 1; i <= n; i ++)
    {
        int two = 0, one = 0, zero = 0;
        for (int j = 0; j < m; j ++)
        {
            if (cnt[j] >= n / 2 + 2)
                two |= (1 << j);
            else
            if (cnt[j] >= n / 2 + 1)
                one |= (1 << j);
            else
            if (cnt[j] >= n / 2)
                zero |= (1 << j);
        }

        int mask = 0;
        for (int j = m - 1; j >= 0; j --)
        {
            mask = mask * 2 + (a[i][j]);
        }

        int ONE = two | (one & (~mask));
        int ZERO = (one & (mask)) | (zero & (~mask));

        ///cout << i << " : " << ONE << " : " << ZERO << endl;
        int ans = 0;
        for (int p = 1; p <= n; p ++)
        {
            if (p == i)
                continue;
                ///cout << "here " << p << " " << ((rev_mask[p])) << endl;
                int cur = __builtin_popcount((rev_mask[p]) & ZERO);
                if (cur > __builtin_popcount(ans))
                    ans = ((rev_mask[p]) & ZERO);
            ///ans = max(ans, __builtin_popcount((~val_mask[p]) & zero));
        }

        ans |= ONE;
        cout << __builtin_popcount(ans) << endl;



    }

}

int main()
{
    ///speed();
    solve();
    return 0;
}

Compilation message

council.cpp: In function 'void solve()':
council.cpp:36:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   36 |         for (int i = 0; i < m; i ++)
      |         ^~~
council.cpp:39:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   39 |             for (int i = 0; i < n; i ++)
      |             ^~~
council.cpp:74:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   74 |             if (p == i)
      |             ^~
council.cpp:77:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   77 |                 int cur = __builtin_popcount((rev_mask[p]) & ZERO);
      |                 ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 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 Incorrect 1 ms 724 KB Output isn't correct
3 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 Execution timed out 4048 ms 8784 KB Time limit exceeded
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 Execution timed out 4048 ms 8784 KB Time limit exceeded
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 Execution timed out 4048 ms 8784 KB Time limit exceeded
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 Execution timed out 4048 ms 8784 KB Time limit exceeded
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 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -