Submission #1089420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089420		Thanhs	Council (JOI23_council)	C++14	100 / 100	1140 ms	121020 KiB

council

#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
 
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 3e5 + 5;
const int MM = 25;
const int EM = (1 << 20) + 5;

struct node
{
    pair<pair<int, int>, pair<int, int>> best = {{0, 0}, {0, 0}};
    node() {}
    node(int a, int b, int c, int d) : best({{a, b}, {c, d}}) {}
    node operator+(const node& o)
    {
        vector<pair<int, int>> v;
        v.push_back(best.fi);
        v.push_back(best.se);
        v.push_back(o.best.fi);
        v.push_back(o.best.se);
        sort(v.begin(), v.end(), [&](const pair<int, int> x, const pair<int, int> y) {return x.fi > y.fi;});
        node res;
        for (auto t : v)
        {
            if (!res.best.fi.se)
                res.best.fi = t;
            else if (!res.best.se.se && t.se != res.best.fi.se)
                res.best.se = t;
        }
        return res;
    }
}dp[EM];

int n, m, a[NM][MM], sum[MM];
pair<int, int> b[EM];

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int msk = 0;
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
            sum[j] += a[i][j];
            msk |= a[i][j] << j;
        }
        (b[msk].fi ? b[msk].se : b[msk].fi) = i;
    }    
    for (int i = 0; i < m; i++)
        for (int j = 0; j < (1 << m); j++)
            if (j >> i & 1)
            {
                if (b[j ^ (1 << i)].fi)
                    (b[j].fi ? b[j].se : b[j].fi) = b[j ^ (1 << i)].fi;
                if (b[j ^ (1 << i)].se)
                    (b[j].fi ? b[j].se : b[j].fi) = b[j ^ (1 << i)].se;
            }
    for (int i = 0; i < (1 << m); i++)
        if (i < (i ^ ((1 << m) - 1)))
            swap(b[i], b[i ^ ((1 << m) - 1)]);
    for (int i = 0; i < (1 << m); i++)
        dp[i] = node(b[i].fi ? __builtin_popcount(i) : 0, b[i].fi, b[i].se ? __builtin_popcount(i) : 0, b[i].se);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < (1 << m); j++)
            if (j >> i & 1)
                dp[j] = dp[j] + dp[j ^ (1 << i)];
    for (int i = 1; i <= n; i++)
    {
        int msk = 0, ans = 0;
        for (int j = 0; j < m; j++)
        {
            if (sum[j] - a[i][j] == n / 2)
                msk |= 1 << j;
            else
                ans += sum[j] - a[i][j] > n / 2;
        }
        cout << ans + (dp[msk].best.fi.se == i ? dp[msk].best.se : dp[msk].best.fi).fi << endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int tc = 1; 
    // cin >> tc;
    while (tc--)
        solve();

}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
council.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 22 / 22
• Subtask 7: 22 / 22