Submission #931028

#TimeUsernameProblemLanguageResultExecution timeMemory
931028KiaRezCouncil (JOI23_council)C++17
100 / 100
2313 ms31824 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define endl '\n' const int N = 3e5+23, lg = 18; ll Mod = 1e9+7; //998244353; inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;} inline ll poww(ll a, ll b, ll mod=Mod) { ll ans = 1; a=MOD(a, mod); while (b) { if (b & 1) ans = MOD(ans*a, mod); b >>= 1; a = MOD(a*a, mod); } return ans; } int n, m, cnt[N], a[N]; pii dp[(1<<20)+10], pd[(1<<20)+1]; inline int get(int m1, int m2) { return __builtin_popcount(m1&m2); } pii merge(int mask, pii x, pii y) { vector<pii> vec; vec.pb({get(a[x.F],mask), -x.F}); vec.pb({get(a[x.S],mask), -x.S}); vec.pb({get(a[y.F],mask), -y.F}); vec.pb({get(a[y.S],mask), -y.S}); sort(all(vec)); return Mp(-vec[0].S, -vec[1].S); } int main () { ios_base::sync_with_stdio(false), cin.tie(0); cin>>n>>m; fill(dp, dp+(1<<m), Mp(0,0)); fill(pd, pd+(1<<m), Mp(0,0)); a[0] = (1<<m)-1; for(int i=1; i<=n; i++) { for(int j=0; j<m; j++) { int bt; cin>>bt; if(bt==1) a[i] += (1<<j), cnt[j]++; } if(dp[a[i]].F == 0) dp[a[i]].F = i; else dp[a[i]].S = i; } for(int i=0; i<m; i++) { for(int mask=0; mask<(1<<m); mask++) { pd[mask] = merge(mask, dp[mask], dp[mask^(1<<i)]); } for(int mask=0; mask<(1<<m); mask++) { dp[mask] = pd[mask]; pd[mask] = Mp(0,0); } } for(int i=1; i<=n; i++) { for(int j=0; j<m; j++) if((a[i]>>j)%2==1) cnt[j] --; int ans = 0, boht=0; for(int j=0; j<m; j++) { if(cnt[j]>=n/2) ans ++; if(cnt[j]==n/2) boht+=(1<<j); } if(dp[boht].F == i) { cout<<ans-get(boht, a[dp[boht].S])<<endl; } else { cout<<ans-get(boht, a[dp[boht].F])<<endl; } for(int j=0; j<m; j++) if((a[i]>>j)%2==1) cnt[j] ++; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...