?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
230753109 |
Дорешивание: racccccoon |
1523D - 184 | C++14 (GCC 6-32) | Полное решение | 576 мс | 2100 КБ | 2023-11-01 04:11:33 | 2023-11-01 04:11:33 |
// LUOGU_RID: 132715755 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=2e5+10; int n,m,p;char ss[N]; LL a[N];int f[1<<15]; bool vis[N]; vector<int>vrr; #define __count __builtin_popcount #define __countLL __builtin_popcountll mt19937 rnd(time(0)); int get() { LL y=rnd()%n+1;return y; } signed main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m>>p; for(int i=1;i<=n;i++) { cin>>ss+1; for(int j=1;j<=m;j++) if(ss[j]=='1')a[i]^=1LL<<(j-1); } LL ans=0; int it,T=min(50,n); int cnt=0; while(T--&&cnt<n) { it=get();++cnt; if(a[it]==0)continue; vrr.clear(); for(int j=1;j<=m;j++) { if(a[it]& (1LL<<(j-1)) ) vrr.push_back(j); } memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { int s=0; for(int j=0;j<vrr.size();j++) { if( a[i] & (1LL<<(vrr[j]-1)) ) s^=1<<j; } f[s]++; } int lim=1<<vrr.size();lim--; for(int j=0;j<vrr.size();j++) { for(int i=1;i<=lim;i++) { if( (i & (1<<j))==0 ) f[i] += f[i ^ (1<<j)]; } } int now=0; for(int i=1;i<=lim;i++) { if(f[i]*2>=n && __count(i) > __count(now) ) now = i; } if( __count(now) > __countLL(ans) ) { ans=0; for(int i=0;i<vrr.size();i++) { if(now&(1<<i))ans|=(1LL<<(vrr[i]-1)); } } } for(int i=1;i<=m;i++) { if(ans&(1LL<<(i-1)))cout<<"1"; else cout<<"0"; }cout<<endl; return 0; }
?
?
?
?