QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#751582 | #7495. 世上最幸福的女孩 | TheZone | 0 | 0ms | 0kb | C++17 | 3.1kb | 2024-11-15 19:30:02 | 2024-11-15 19:30:03 |
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define mod 998244353
struct modint{
int x;
modint(int o=0){x=o;}
modint &operator = (int o){return x=o,*this;}
modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
modint &operator ^=(int b){
modint a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint &operator /=(modint o){return *this *=o^=mod-2;}
friend modint operator +(modint a,modint b){return a+=b;}
friend modint operator -(modint a,modint b){return a-=b;}
friend modint operator *(modint a,modint b){return a*=b;}
friend modint operator /(modint a,modint b){return a/=b;}
friend modint operator ^(modint a,int b){return a^=b;}
friend bool operator ==(modint a,int b){return a.x==b;}
friend bool operator !=(modint a,int b){return a.x!=b;}
bool operator ! () {return !x;}
modint operator - () {return x?mod-x:0;}
bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}
vector<modint> fac,ifac,iv;
inline void initC(int n)
{
if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
int m=iv.size(); ++n;
if(m>=n)return;
iv.resize(n),fac.resize(n),ifac.resize(n);
For(i,m,n-1){
iv[i]=iv[mod%i]*(mod-mod/i);
fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
}
}
inline modint C(int n,int m){
if(m<0||n<m)return 0;
return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 300005
#define inf 0x3f3f3f3f
int n,m;
int a[maxn][22],b[maxn];
int cnt[maxn];
struct node{
pii x,y;
void ins(pii z){
if(z.se==x.se || z.se==y.se)return;
if(z>x)y=x,x=z;
else if(z>y)y=z;
}
}mx[1<<20],hav[1<<20];
signed main()
{
n=read(),m=read();
For(i,1,n){
int S=0;
For(j,0,m-1)a[i][j]=read(),cnt[j]+=a[i][j],S|=((!a[i][j])<<j);
hav[S].ins(mkp(1,i));
b[i]=S;
}
For(i,0,m-1)For(s,0,(1<<m)-1)if(s>>i&1)
hav[s^(1<<i)].ins(hav[s].x),hav[s^(1<<i)].ins(hav[s].y);
For(i,0,(1<<m)-1)
{
int c=__builtin_popcount(i);
if(hav[i].x.se) mx[i].ins(mkp(c,hav[i].x.se));
if(hav[i].y.se) mx[i].ins(mkp(c,hav[i].y.se));
}
For(i,0,m-1)
For(s,0,(1<<m)-1)
if(s>>i&1)
mx[s].ins(mx[s^(1<<i)].x),
mx[s].ins(mx[s^(1<<i)].y);
For(i,1,n){
int res=0,nd=0;
For(j,0,m-1){
cnt[j]-=a[i][j];
if(cnt[j]-1>=n/2)++res;
else if(cnt[j]>=n/2)nd|=(1<<j);
}
if(i==mx[nd].x.se)res+=mx[nd].y.fi;
else res+=mx[nd].x.fi;
if(i==3){
}
cout<<res<<"\n";
For(j,0,m-1)cnt[j]+=a[i][j];
}
return 0;
}
詳細信息
Pretests
Final Tests
Test #1:
score: 0
Time Limit Exceeded
input:
300000 600000 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36 -37 -38 -39 -40 -41 -42 -43 -44 -45 -46 -47 -48 -49 -50 -51 -52 -53 -54 -55 -56 -57 -58 -59 -60 -61 -62 -63 -64 -65 -66 -67 -68 -69 -70 -71 -72 -73 -74...
output:
result:
Test #2:
score: 0
Time Limit Exceeded
input:
300000 600000 -6000 -12000 -18000 -24000 -30000 -36000 -42000 -48000 -54000 -60000 -66000 -72000 -78000 -84000 -90000 -96000 -102000 -108000 -114000 -120000 -126000 -132000 -138000 -144000 -150000 -156000 -162000 -168000 -174000 -180000 -186000 -192000 -198000 -204000 -210000 -216000 -222000 -228000...
output:
result:
Test #3:
score: 0
Runtime Error
input:
300000 600000 694739332 12000 18000 24000 30000 36000 42000 48000 54000 60000 66000 72000 78000 84000 90000 96000 102000 108000 114000 120000 126000 132000 138000 805133449 150000 156000 162000 168000 174000 180000 186000 192000 198000 204000 210000 216000 222000 372033439 234000 240000 246000 25200...
output:
result:
Test #4:
score: 0
Runtime Error
input:
300000 600000 -370584886 -824446876 -217953152 -213883201 -3695086 -244661761 -31643401 -28513584 -120242422 -164834515 -442171367 -44150185 -373313047 -176037889 -88006209 13397 -137034887 -288429275 -105994131 9344897 -561275521 -739928113 -410398492 -766560640 -234474561 -376898910 -3876489 -7672...
output:
result:
Test #5:
score: 0
Runtime Error
input:
300000 600000 211880591 88968133 407526653 911890111 807256887 -176021101 106280356 8936401 282861019 5357877 254177 417572162 -357964741 -381515641 129902155 473664349 -59617567 667379417 776235315 58916209 7886485 223802672 -47045571 804252695 203831125 43372991 28892923 158908981 378392554 -30512...
output:
result:
Test #6:
score: 0
Runtime Error
input:
300000 600000 478547749 21607029 -89838541 489455731 -26326441 -57796177 11291418 580134112 194452929 323639427 78318073 26812402 543586369 370325145 -15025771 77970751 -57165081 69553200 68373559 103525821 488338363 -114852353 129257857 353303549 120029521 55251574 184069369 116347321 66298177 2323...
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
300000 600000 -167628 147836 342193 -113005 335767 62551 37153 391126 62081 394393 64376 61561 204691 362478 -192721 246628 -34842 558316 210421 492772 63566 -119326 208751 549977 400921 424726 242537 401281 -156335 392551 175009 213401 277477 510111 27205 90706 544489 166673 325195 362819 -1502 497...
output:
result:
Test #8:
score: 0
Runtime Error
input:
300000 600000 -52710799 -139860657 -76037377 -383460841 -250485933 -170800931 38569417 -148104385 -366126471 36758571 61991329 -179464171 -336298825 -58594900 22133163 -423137793 -364236327 37740025 -191822446 -86831549 68026423 -113477261 -80044118 -45362365 -154807957 -29767662 -474689591 -1954812...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
300000 600000 -9317 -17721 83807 -89601 -132992 -21217 -164947 -15601 -168899 190720 -33799 -114351 -91457 -194029 132053 -109571 -65991 -107846 -77121 -90550 -162626 -66021 -52064 -69881 55395 -187207 -41697 -152345 76528 -97151 -172721 100673 -190401 -29409 -62929 -112268 -92705 -165993 -61056 -37...
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
300000 600000 -9317 -17721 83807 -89601 -132992 -21217 -164947 -15601 -168899 190720 -33799 -114351 -91457 -194029 132053 -109571 -65991 -107846 -77121 -90550 -162626 -66021 -52064 -69881 55395 -187207 -41697 -152345 76528 -97151 -172721 100673 -190401 -29409 -62929 -112268 -92705 -165993 -61056 -37...
output:
result:
Test #11:
score: 0
Time Limit Exceeded
input:
300000 600000 -350031 -418621 -379153 -349541 -204935 -413677 -290785 -73634 -339579 -86194 -237211 -393502 -477091 -479966 -452057 -384481 -843294 -221408 -132345 -109333 -149097 -483897 -29033 -220275 -50099 -39225 -148729 -397731 -222829 -436818 -233585 -433945 -335641 -44285 -107328 -338151 -534...
output:
result:
Test #12:
score: 0
Time Limit Exceeded
input:
300000 600000 -696987827 1791548840 1540245114 -744556712 281332436 -396365348 -660700017 -926408705 66098449 1448486061 -1945919603 1080362360 732219815 -519568302 1228792006 364734706 -1151351486 -1056003603 -1852483513 -1758573146 762059937 -333873273 -1645890512 1388909837 -267565502 1028489524 ...