Submission #921689

#	Time	Username	Problem	Language	Result	Execution time	Memory
921689		vjudge1	Council (JOI23_council)	C++17	41 / 100	4046 ms	41596 KiB

council

#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define str string
#define fastio ios::sync_with_stdio(0), cin.tie(0);
#define fs first
#define ss second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define len(x) x.size()

#define print(a)          \
    for (auto &x : a)     \
        cout << x << " "; \
    cout << endl;

#define printmp(a)    \
    for (auto &x : a) \
        cout << x.fs << " " << x.ss << endl;

const int mod = 998244353;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    map<vector<int>, int> dist;
    vector<vector<int>> p;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j ++)
            cin >> a[i][j];
        if(dist.find(a[i]) == dist.end()){
            dist[a[i]] = p.size();
            p.push_back({});
            p[p.size() - 1].push_back(i);
        }
        else{
            p[dist[a[i]]].push_back(i);
        }
    }
    vector<int> cnt(m);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cnt[j] += a[i][j];
    vector<vector<int>> important;
    vector<int> res;
    for(auto x : dist){
        important.push_back({});
        res.push_back(0);
        for(int j = 0; j < m; j ++){
            cnt[j] -= x.fs[j];
            if(cnt[j] == n / 2)
                important[important.size() - 1].push_back(j);
            if(cnt[j] >= n / 2)
                res[res.size() - 1] ++;
            cnt[j] += x.fs[j];
        }
    }
    vector<int> ans(n);
    int j = 0;
    for(auto x : dist){
        int mn = res[j];
        for(auto y : dist){
            int nums = 0;
            if(y != x or p[x.ss].size() >= 2){
                for(auto k : important[j])
                    nums += y.fs[k];
                mn = min(mn, nums);
            }
        }
        for(auto y : p[x.ss])
            ans[y] = res[j] - mn;
        for(int j = 0; j < m; j ++)
            cnt[j] += x.fs[j];
        j ++;
    }
    print(ans)
}

signed main()
{
    fastio int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        // cout << endl;
    }
}

Compilation message (stderr)

council.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize("Ofast")
      | 
council.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("Ofast")
      | 
council.cpp:4: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    4 | #pragma optimize(Ofast)
      |

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