Submission #52119403

---

Source Code Expand

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)

static constexpr size_t bitsize = 16000; // 4000000の約数
bitset<bitsize> bit[2000];
int B = 4000000 / bitsize; // N * M = 4000000

int main() { 
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vector a(n, vector(m, 0));
    rep(i, n) rep(j, m) cin >> a[i][j];

    int id = 0;
    vector pari(n, vector(n, 0));
    rep(j, m) {
        vector<vector<int>> v(1000); // max(A) = 1000
        rep(i, n) v[a[i][j]].push_back(i);
        rep(i, 1000) {
            int sz = v[i].size();
            if(sz >= B) {
                for(int e : v[i]) bit[e].set(id);
                id ++;
            } else if(sz > 1) {
                rep(x, sz) for(int y = x + 1; y < sz; y ++) {
                    pari[v[i][x]][v[i][y]] ^= 1;
                }
            }
        }
    }
    int ans = 0;
    rep(i, n) for(int j = i + 1; j < n; j ++) {
        if(((bit[i] & bit[j]).count() & 1) ^ pari[i][j]) ans ++;
    }
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result