Submission #918381

#TimeUsernameProblemLanguageResultExecution timeMemory
918381gs25Council (JOI23_council)C++17
62 / 100
284 ms57940 KiB
#include <bits/stdc++.h> using namespace std; void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifndef ONLINE_JUDGE #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define dbg(x...) #endif #define rrep(i,n) for(int i=1; i<=n; i++) #define rep(i,n) for(int i=0; i<n; i++) #define all(v) (v).begin(), (v).end() #define ff first #define ss second #define pb push_back int popcnt(int x){ assert(x>=0); return __builtin_popcount(x); } int N,M; const int MAXN = 300100; int x[MAXN]; int p[30]; int cnt[MAXN]; long long dp[30][3000000]; int comb[300][300]; void solve(){ comb[1][0] = 1; comb[1][1] = 1; for(int i=2; i<=22; i++){ for(int j=0; j<=i; j++){ comb[i][j] = comb[i-1][j]+(j!=0 ? comb[i-1][j-1] : 0); } } cin >> N >> M; int k = N/2; const int MSK = (1<<M) - 1; rep(i,N){ rep(j,M){ int a; cin >> a; if(a==0) continue; p[j] += a; x[i] |= (1<<j); } x[i] = MSK^x[i]; } int zeros=0, ones=0, twos=0; rep(j,M){ if(p[j]>=k+2) zeros |= (1<<j); if(p[j]==k+1) ones |= (1<<j); if(p[j]==k) twos |= (1<<j); } rep(i,N) cnt[x[i]]++; for(int i=0; i<M; i++){ for(int j=0; j<=MSK; j++){ if( (j & (1<<i)) ==0) { cnt[j] += cnt[j^(1<<i)]; } } } for(int j=0; j<= MSK; j++) dp[popcnt(j)][j] = cnt[j]; for(int i=0; i<M; i++){ for(int j=0; j<=MSK; j++){ if(j&(1<<i)){ rep(k,M) dp[k][j] += dp[k][j^(1<<i)]; } } } rep(i,N){ int tmp = (ones&(MSK^x[i])) | (twos&(x[i])); assert(tmp>=0 && tmp<=MSK); // tmp maximize tmp | x[j]; int MM = 0; bool flag = false; long long sum = 0, first_big=0, id=0; for(int k=M; k>0; k--){ assert(tmp>=0 && tmp<=MSK); if(!flag && dp[k][tmp]>0LL){ if(popcnt(tmp&x[i])!=k){ MM = k; break; } flag=true; if(dp[k][tmp]>1){ MM = k; break; } first_big=k; sum = 1; id = 1; continue; } if(flag){ assert(id<30 && first_big < 30); sum = comb[first_big][id++]; if(dp[k][tmp]>sum){ MM = k; break; } } } cout << MM + popcnt(zeros|(ones&x[i])) << "\n"; } } int32_t main(void){ ios::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr); int t =1; // cin >> t; while(t--) solve(); }
#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...