Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
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;
}
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования