| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 731606 |
2023-04-27T16:11:45 Z |
grogu |
Council (JOI23_council) |
C++14 |
|
4000 ms |
16228 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
752 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
752 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Execution timed out |
4009 ms |
16228 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Execution timed out |
4009 ms |
16228 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Execution timed out |
4009 ms |
16228 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Execution timed out |
4009 ms |
16228 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
752 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
