CF2038I Polyathlon 题解

这里是赛时非正解做法。话说这题是被榜带歪了吧。

考虑阈值分治，记 V=nm=2\times 10^6，设一个阈值 B。对于 n\le B 的时候，考虑如下做法：枚举一对点 (i,j)，我们想知道在哪些位置开始一轮比赛才不会让 i 被淘汰，也就是所有 a_{i,x}=1,a_{j,x}=0 的位置 x，到环上之前第一个 a_{i,x}=0,a_{j,x}=1 的位置是合法的。因为保证每个位置被扫描和覆盖最多一次，复杂度 O(n^2m)=O(BV)。

否则 n>B，直接模拟题意是 O(nm^2) 的，但是可以 bitset 优化，但是它是静态定长的很烦。注意到此时 m>\log B，所以 bitset 只需要开到 \frac{nm}{\log B}，复杂度 O(\frac{nm^2}{\omega \log B})=O(\frac{V^2}{B\omega\log B})。

近似一下，平衡 B 即可做到 O(V\sqrt{\frac{V}{\omega \log V}})。可以适当加一下诸如 n\le B 的部分对枚举 j 的顺序随机打乱，对 n>B 的部分再次阈值分治优化一下 bitset 长度等等。

#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
#include <random>
#include <ctime>
using namespace std;

mt19937 rnd(time(NULL));
int n,m,B=400;
char c[1000005];
int ans[1000005];
vector <bool> a[1000005];

inline void in(int &n){
    n=0;
    char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
    return ;
}

namespace sub1{
    int id[10005];
    bool ok[1000005];
    bool oo[1000005];
    inline void work(){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) ok[j]=1;
            for(int j=1;j<=n;j++) id[j]=j;
            shuffle(id+1,id+1+n,rnd);
            for(int j=1;j<=n;j++){
                int x=id[j];
                if(i==x) continue;
                for(int k=1;k<=m;k++) oo[k]=0;
                for(int k=1;k<=m;k++){
                    if(a[x][k]) continue;
                    if(a[x][k]==a[i][k]) continue;
                    int pos=k;
                    while(1){
                        if(a[x][pos]&&!a[i][pos]) break;
                        oo[pos]=ok[pos];
                        pos--;
                        if(pos==0) pos=m;
                        if(pos==k) break;
                    }
                }
                bool ko=0;
                for(int k=1;k<=m;k++) ok[k]=oo[k],ko|=ok[k];
                if(!ko) break;
            }
            for(int j=1;j<=m;j++) if(ok[j]) ans[j]=i;
        }
        for(int i=1;i<=m;i++) printf("%d ",ans[i]);
        return ;
    }
}

namespace sub2{
    inline void work1(){
        bitset <100005> f,g;
        bitset <100005> aa[5005];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) aa[j][i]=a[i][j];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++) f[j]=1;
            int x=i;
            while(1){
                g=f&aa[x];
                if(g.any()) f=g;
                x=x%m+1;
                if(x==i) break;
            }
            x=0;
            for(int j=1;j<=n;j++) if(f[j]) x=j;
            printf("%d ",x);
        }

        return ;
    }
    inline void work2(){
        bitset <5005> f,g;
        bitset <5005> aa[5005];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) aa[j][i]=a[i][j];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++) f[j]=1;
            int x=i;
            while(1){
                g=f&aa[x];
                if(g.any()) f=g;
                x=x%m+1;
                if(x==i) break;
            }
            x=0;
            for(int j=1;j<=n;j++) if(f[j]) x=j;
            printf("%d ",x);
        }

        return ;
    }
    inline void work(){
        if(n<=5000) work2();
        else work1();
        return ;
    }
}

int main(){
    in(n),in(m);
    for(int i=1;i<=n;i++){
        a[i].resize(m+1);
        // for(int j=1;j<=m;j++) a[i][j]=(i+j)&1;
        // for(int j=1;j<=m;j++) a[i][j]=1;
        // a[i][i]=0;
        scanf("%s",c+1);
        for(int j=1;j<=m;j++) a[i][j]=c[j]-'0';
    }
    if(n<=B){sub1::work();return 0;}
    sub2::work();

    return 0;
}