Submission #731606

#	Time	Username	Problem	Language	Result	Execution time	Memory
731606		grogu	Council (JOI23_council)	C++14	0 / 100	4009 ms	16228 KiB

council

#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
**/

Compilation message (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);
      |            ^~~~~~

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