제출 #731606

#제출 시각아이디문제언어결과실행 시간메모리
731606groguCouncil (JOI23_council)C++14
0 / 100
4009 ms16228 KiB
#define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include <bits/stdc++.h> #define ld double #define ll long long #define ull unsigned long long #define llinf 100000000000000000LL // 10^17 #define iinf 2000000000 // 2*10^9 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pii pair<int,int> #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() using namespace std; #define maxn 3000005 #define maxx 20000005 #define lg 20 ll n,m; ll a[maxn]; pll d[maxx][2]; pll ans[maxx][2]; ll cnt[lg]; ll klk[maxx]; bool cmp(pll x,pll y){return x.fi>y.fi;} int main(){ ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); cin >> n >> m; for(ll i = 1;i<=n;i++){ for(ll j = 0;j<m;j++){ ll x; cin >> x; if(x) a[i]+=(1<<j); cnt[j]+=x; } klk[a[i]]++; } for(ll i = 0;i<(1<<m);i++) d[i][0] = d[i][1] = {llinf,-1}; queue<pair<pll,ll> > q; for(ll i = 1;i<=n;i++){ ll svi = (1<<m)-1; //a[i]^=svi; d[a[i]][0] = {0,a[i]}; q.push({d[a[i]][0],a[i]}); //a[i]^=svi; } while(q.size()){ ll u = q.front().sc; ll cur = q.front().fi.fi; ll poc = q.front().fi.sc; q.pop(); if(cur>d[u][1].fi) continue; for(ll j = 0;j<m;j++){ ll s = u^(1<<j); if(cur+1<d[s][0].fi){ d[s][1] = d[s][0]; d[s][0] = {cur+1,poc}; q.push({d[s][0],s}); }else if(cur+1<d[s][1].fi&&u!=d[s][1].sc){ d[s][1] = {cur+1,poc}; q.push({d[s][1],s}); } } } for(ll x = 0;x<(1<<m);x++){ ll y = (1<<m) - 1 - x; ll svi = (1<<m) - 1; ll bits = m - __builtin_popcount(x); ans[x][0] = d[x^svi][0]; ans[x][1] = d[x^svi][1]; ans[x][0].fi-=bits; ans[x][1].fi-=bits; for(ll i = y;i;i = (i-1)&y){ vector<pll> v; v.pb(ans[x][0]); v.pb(ans[x][1]); ll e = (i+x)^svi; pll p = d[e][0]; pll q = d[e][1]; p.fi-=bits; q.fi-=bits; v.pb(p); v.pb(q); sort(all(v),cmp); ans[x][0] = v[0]; for(ll k = 1;k<=3;k++){ if(v[k].sc!=v[0].sc){ ans[x][1] = v[k]; break; } } } } bool debug = 0; if(debug){ for(ll i = 0;i<(1<<m);i++){ dbg(i); cerr<<ans[i][0].fi<< " "<<ans[i][0].sc<<endl; cerr<<ans[i][1].fi<< " "<<ans[i][1].sc<<endl; } here; for(ll i = 0;i<(1<<m);i++){ dbg(i); cerr<<d[i][0].fi<< " "<<d[i][0].sc<<endl; cerr<<d[i][1].fi<< " "<<d[i][1].sc<<endl; } here; } for(ll i = 1;i<=n;i++){ for(ll j = 0;j<m;j++){ if((1<<j)&a[i]) cnt[j]--; } ll y = 0; ll cur = 0; for(ll j = 0;j<m;j++){ if(cnt[j]==n/2){ y+=(1<<j); } if(cnt[j]>=n/2) cur++; } dbg(y); dbg(cur); pll p = ans[y][0]; pll q = ans[y][1]; dbg(p.fi); ll popcnt = __builtin_popcount(y); if(p.sc!=a[i]||(p.sc==a[i]&&klk[a[i]]>1)){ cout<<cur-p.fi<<endl; }else{ cout<<cur-q.fi<<endl; } for(ll j = 0;j<m;j++){ if((1<<j)&a[i]) cnt[j]++; } } return 0; } /** 3 3 1 0 0 1 1 0 1 1 1 4 12 1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 4 2 1 0 0 1 1 1 1 1 **/

컴파일 시 표준 에러 (stderr) 메시지

council.cpp: In function 'int main()':
council.cpp:44:12: warning: unused variable 'svi' [-Wunused-variable]
   44 |         ll svi = (1<<m)-1;
      |            ^~~
council.cpp:129:12: warning: unused variable 'popcnt' [-Wunused-variable]
  129 |         ll popcnt = __builtin_popcount(y);
      |            ^~~~~~
#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...