Submission #34029401

---

Source Code Expand

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
mt19937 gen32(time(0));
#define SZ 2666666
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
typedef pair<int,int> pii;
typedef long long ll;
int n,k,S;
int id(int x,int y,int r=0) {
    if(r) return y*S+x;
    return x*S+y;
}
int gx(int t) {
    return t/S;
}
int gy(int t) {
    return t%S;
}
bool valid(int t) {
    return t/S>=1&&t/S<=n&&t%S>=1&&t%S<=n;
}
int rpos() {
    return (gen32()%n+1)*S+gen32()%n+1;
}
struct UFS {
int ff[SZ],cn[SZ][6],sz[SZ];
void clear() {
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) {
            int s=id(i,j); ff[s]=0; sz[s]=1;
            memset(cn[s],0,sizeof cn[s]);
        }
}
int find(int a) {
    if(!ff[a]) return a;
    return ff[a]=find(ff[a]);
}
bool link(int a,int b) {
    int x=find(a),y=find(b);
    if(x!=y) ff[x]=y,sz[y]+=sz[x];
    return x!=y;
}
int gsz(int x) {
    return sz[find(x)];
}
}U;
int we[2333];
int B=SZ/3,ea[SZ],eb[SZ],ek[SZ],ms[SZ],vv[SZ];
struct arr {
int w[101*101];
vector<pii> mvs;
void add_move(int s,int d) {
    assert(valid(s)&&valid(s+d)&&w[s]<0&&w[s+d]==0);
    mvs.push_back(make_pair(s,d));
    w[s+d]=w[s]; w[s]=0;
}
void initufs() const {
    U.clear();
    for(int i=1;i<=n;++i)
        for(int j=1,b;j<=n;++j) if((b=w[id(i,j)])>0) U.link(ea[b],eb[b]);
}
//(val, num_cc)
pair<pii,int> stats() const {
    initufs();
    for(int i=1;i<=n;++i)
        for(int j=1,b;j<=n;++j) if((b=w[id(i,j)])<0) ++U.cn[U.find(id(i,j))][-b];
    int ans=0,num_cc=0,ans2=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) {
            int o=id(i,j),ct=0;
            if(U.ff[o]||w[o]>=0) continue;
            int*cn=U.cn[o]; ++num_cc;
            for(int s=1;s<=k;++s) {
                ans-=ct*cn[s]; ct+=cn[s];
                ans+=cn[s]*(cn[s]-1)/2;
                ans2+=we[s]*cn[s]*(cn[s]-1)/2;
            }
        }
    return make_pair(make_pair(ans,ans2),num_cc);
}
bool validate(int lb=-1e9) const {
    auto st=stats();
    return (int)mvs.size()<=st.se&&st.fi.se>lb;
}
int gap() const {
    return stats().se-(int)mvs.size();
}
pii val() const {
    return stats().fi;
}
void add_bridge(int x,int y,int d) {
    ++B; ea[B]=x; eb[B]=y; ek[B]=d;
    for(int p=x;p!=y;p+=d)
        if(w[p]==0) w[p]=B;
        else if(p!=x) {
            cerr<<x<<"~"<<y<<"  "<<d<<" but at "<<p<<":"<<w[p]<<"  "<<gx(x)<<","<<gy(x)<<" "<<gx(y)<<","<<gy(y)<<"\n";
            dbg();
            assert(p==x);
        }
}
void reset_bridge(int bid) {
    for(int p=ea[bid];p!=eb[bid];p+=ek[bid]) {
        if(w[p]>0) {
            assert(w[p]==bid);
            w[p]=0;
        }
    }
}
bool bridge_ready(int x,int y,int g) {
    for(int p=x;p!=y;p+=g) if(w[p]>0) return false;
    return true;
}
void smart_greedy(int rep_max=1) {
    mt19937 mygen(23333);
    static int best_val;
    static arr best_rst;
    if(rep_max>1) {
        best_val=val().se;
        best_rst=*this;
    }
    for(int rep=0;rep<rep_max;++rep) {
        initufs();
        vector<array<int,3>> v;
        static int st[SZ];
        for(int dir=0;dir<2;++dir)
            for(int i=1;i<=n;++i) {
                int sn=0;
                for(int j=1;j<=n;++j) if(w[id(i,j,dir)]) st[++sn]=j;
                for(int j=1;j<sn;++j) {
                    int l=st[j],r=st[j+1];
                    if(w[id(i,l,dir)]<0&&w[id(i,l,dir)]==w[id(i,r,dir)]) {
//                        if(!validc(-w[id(i,l,dir)])) continue;
                        int x=id(i,l,dir),y=id(i,r,dir),p=dir?S:1;
                        v.push_back(array<int,3>{x,y,p});
                    }
                }
            }
        static vector<int> yg[SZ];
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j) yg[id(i,j)].clear();
        static int vvs[SZ],CC=0;
        ++CC;
        priority_queue<pii> pq;
        auto cons=[&](int i) {
            pq.push(pii(U.gsz(v[i][0])*U.gsz(v[i][1]),i));
        };
        for(int i=0;i<(int)v.size();++i) {
            yg[U.find(v[i][0])].push_back(i);
            yg[U.find(v[i][1])].push_back(i);
            cons(i);
        }
//        set<int> vvs;
        while(!pq.empty()) {
            int i=pq.top().se; pq.pop();
            if(vvs[i]==CC) continue;
            vvs[i]=CC;
            int gx=U.find(v[i][0]),gy=U.find(v[i][1]);
            if(gx==gy||!bridge_ready(v[i][0],v[i][1],v[i][2]))
                continue;
            add_bridge(v[i][0],v[i][1],v[i][2]);
            if(yg[gx].size()>yg[gy].size()) swap(gx,gy);
            U.ff[gx]=gy; U.sz[gy]+=U.sz[gx];
            auto&ygy=yg[gy];
            for(auto t:yg[gx]) if(vvs[t]-CC) ygy.push_back(t);
            for(auto a:ygy) if(vvs[a]-CC) cons(a);
        }
        if(rep_max>1) {
            auto cvv=val().se;
            if(cvv>best_val) {
                best_val=cvv;
                best_rst=*this;
            }
        }
        if(rep+1<rep_max) {
            set<int> bri;
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j) if(w[id(i,j)]>0) bri.insert(w[id(i,j)]);
            for(auto t:bri) if(mygen()%3==0) reset_bridge(t);
        }
    }
    if(rep_max>1)
        *this=best_rst;
    auto g=gap();
    if(g>=0) return;
    while(g<0) {
        initufs();
        static pii bris[SZ]; int bn=0;
        for(int i=1;i<=n;++i)
            for(int j=1,b;j<=n;++j) if((b=w[id(i,j)])>0) bris[++bn]=pii(-U.gsz(ea[b]),b);
        sort(bris+1,bris+1+bn);
        bn=unique(bris+1,bris+1+bn)-(bris+1);
        for(int cnt=0;cnt<10&&g<0;++cnt) {
            ++g; auto t=bris[bn--];
            reset_bridge(t.se);
        }
    }
}
void dbg() const {
    printf("total %d lines [ST]\n",n);
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=n;++j) {
            int s=id(i,j);
            if(w[s]<=0) printf("%d",-w[s]);
            else printf("%c"," abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"[w[s]%52+1]);
        }
        printf("\n");
    }
    printf("total %d lines [ED]\n",n);
}
void clean_junk() {
    set<int> bs;
    for(int i=1;i<=n;++i)
        for(int j=1,b;j<=n;++j) if((b=w[id(i,j)])>0) bs.insert(b);
    vector<int> bs_sf(all(bs));
    shuffle(all(bs_sf),gen32);
    U.clear();
    for(auto b:bs_sf)
        if(!U.link(ea[b],eb[b])) {
            reset_bridge(b);
            continue;
        }
}
string output() const {
    set<pii> cons;
    for(int i=1;i<=n;++i)
        for(int j=1,b;j<=n;++j)
            if((b=w[id(i,j)])>0) cons.insert(mp(ea[b],eb[b]));
    stringstream t;
    t<<mvs.size()<<"\n";
    for(auto m:mvs) {
        int x1=gx(m.fi),y1=gy(m.fi),x2=gx(m.fi+m.se),y2=gy(m.fi+m.se);
        assert(x1%2==1&&y1%2==1&&x2%2==1&&y2%2==1);
        t<<x1/2<<" "<<y1/2<<" "<<x2/2<<" "<<y2/2<<"\n";
    }
//        t<<gx(m.fi)-1<<" "<<gy(m.fi)-1<<" "<<gx(m.fi+m.se)-1<<" "<<gy(m.fi+m.se)-1<<"\n";
//    printf("0\n"); // no moves so far
    vector<pii> op;
    U.clear();
    for(auto c:cons) {
        if(!U.link(c.fi,c.se)) continue;
        op.pb(c);
    }
    t<<op.size()<<"\n";
//    printf("%d\n",(int)op.size());
    for(auto c:op) {
        int x1=gx(c.fi),y1=gy(c.fi),x2=gx(c.se),y2=gy(c.se);
        assert(x1%2&&y1%2&&x2%2&&y2%2);
        t<<x1/2<<" "<<y1/2<<" "<<x2/2<<" "<<y2/2<<"\n";
//        printf("%d %d %d %d\n",x1,y1,x2,y2);
    }
    return t.str();
}
bool sample_erase() {
    if(mvs.empty()) return 0;
    int r=gen32()%mvs.size();
    int so=mvs[r].fi,tg=so+mvs[r].se;
    for(int j=r+1;j<(int)mvs.size();++j)
        if(mvs[j].fi==tg||mvs[j].se+mvs[j].fi==tg
        ||mvs[j].fi==so||mvs[j].se+mvs[j].fi==so) return 0;
    assert(w[tg]<0);
    mvs.erase(mvs.begin()+r);
    if(w[so]>0) reset_bridge(w[so]);
    for(int d:{1,-1,S,-S}) {
        int b;
        if(valid(tg+d)&&(b=w[tg+d])>0&&(ea[b]==tg||eb[b]==tg)) reset_bridge(b);
    }
    assert(so!=tg);
    assert(valid(so)&&valid(tg));
    w[so]=w[tg]; w[tg]=0;
//    validate();
    return 1;
}
void clear_bridges() {
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) {
            auto&s=w[id(i,j)];
            if(s>0) s=0;
        }
}
}best,cur;
inline pair<pii,arr> add_freebie(arr t) {
    t.smart_greedy(5);
    return make_pair(t.val(),t);
}
pii add_freebie_val(arr t) {
    return add_freebie(t).fi;
}
void reassign_bridge_id() {
    // new edges at [1/3,2/3]
    // move everything to [2/3,1], and then move back to [0,1/3]
    static int C=0;
    for(int st=SZ/3*2;st>=0;st-=max(st,1)) {
        ++C; int A=st;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) {
                int t=id(i,j); auto &v=best.w[t];
                if(v>0) {
                    if(vv[v]!=C) {
                        vv[v]=C; ms[v]=++A;
                        ea[A]=ea[v]; eb[A]=eb[v]; ek[A]=ek[v];
                    }
                    v=ms[v];
                }
            }
    }
    B=SZ/2;
}
void input() {
    cin>>n>>k; S=n*2+1;
    assert(k<=5);
    for(int i=1;i<=n;++i) {
        string l; cin>>l;
        for(int j=1;j<=n;++j) {
            int c=l[j-1]-'0';
            assert(0<=c&&c<=k);
            best.w[id(i*2-1,j*2-1)]=-c;
        }
    }
    n=n*2-1;
    cur=best;
}
#ifndef ONLINE_JUDGE
//#define ENDLESS_TEST
#endif
int eval(int c) {
    vector<pii> vp;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(cur.w[id(i,j)]==-c) vp.pb(pii(i,j));
    int ans=0;
    for(auto t:vp) {
        int mi=2e9;
        for(auto s:vp) if(t!=s) {
            auto a=t,b=s;
            for(int d=0;d<2;++d) {
            if(a.fi>b.fi) swap(a,b);
            int ca=abs(a.fi-b.fi);
            for(int g=a.fi;g<=b.fi&&ca<mi;++g) {
                for(int u=min(a.se,b.se);u<=max(a.se,b.se);++u) {
                    int o=cur.w[id(g,u,d)];
                    ca+=o&&o!=-c;
                }
                if(ca>=mi) break;
                for(int u=a.fi;u<=g;++u) {
                    int o=cur.w[id(u,a.se,d)];
                    ca+=o&&o!=-c;
                }
                if(ca>=mi) break;
                for(int u=g;u<=b.fi;++u) {
                    int o=cur.w[id(b.se,u,d)];
                    ca+=o&&o!=-c;
                }
            }
            mi=min(mi,ca);
            swap(a.fi,a.se);
            swap(b.fi,b.se);
            }
        }
        ans+=mi;
    }
    return ans;
}
int main() {
    input();
    vector<pii> ve;
    for(int i=1;i<=k;++i) ve.pb(mp(eval(i),i));
    sort(ve.begin(),ve.end());
    for(int i=1;i<=k;++i) we[i]=1;
    for(int i=0;i<2&&i<ve.size();++i) we[ve[i].se]=(3-i)*3;
    const int dir[]={2,-2,2*S,-2*S};
    int nxt_rb=0,og=-1;
    int best_val=-1;
    int last_gap=2e9;
    int last_se=-1;
    arr best_arr; // debug only!!!
    string best_op;
    int ty=0;
    add_freebie(cur).se.initufs();
    while(1) {
        #ifndef ENDLESS_TEST
        if(clock()>=CLOCKS_PER_SEC*2.8) break;
        #endif
        if(--nxt_rb>=0) {
            while(gen32()%5)
                if(gen32()%(7-max(5-last_gap/10,0))==0)
                    cur.sample_erase();
            int csb=0,bestv=-1;
            vector<int> info;
            for(int att=1;att<=300&&csb<20;++att) {
                /**/
                int x=0; while(cur.w[x]>=0) x=rpos();
                int mv=0;
//                cerr<<"B";
                if(gen32()%3) {
                    int t=gen32()%4; mv=dir[t];
                    bool good=valid(x+mv)&&cur.w[x+mv]==0;
                    if(!good) continue;
                }
                int d=mv;
                while(d==mv||d==-mv) d=dir[gen32()%4];
//                cerr<<"C";
                int y=x+mv+d;
                while(valid(y)&&cur.w[y]>=0) y+=d;
                if(!valid(y)) continue;
                int sk1=-1,md=0;
                if(cur.w[x]!=cur.w[y]) {
//                    if(mv) continue;
                    for(auto dd:dir) if(valid(y+dd)) {
                        if(dd!=d&&dd!=-d&&cur.w[y+dd]==0) {
                            if(!md||gen32()%2) md=dd;
                        }
                    }
                    if(!md) continue;
                    sk1=y; y+=d;
                    while(valid(y)&&cur.w[y]>=0) y+=d;
                    if(!valid(y)) continue;
                    if(cur.w[x]!=cur.w[y]) continue;
                }
                if(U.find(x)==U.find(y)) continue;
                if(!mv&&sk1==-1) continue;
                auto ps=U.gsz(x)*U.gsz(y);
                //x^2/2 -> (x/2)^2/2
                if(sk1!=-1&&U.gsz(sk1)*U.gsz(sk1)/2>ps&&ty) continue;
                if(ps>bestv)
                    bestv=ps, info={ps,sk1,md,x,mv}, ++csb;
                /*
                if(sk1!=-1)
                    cur.add_move(sk1,md);
                if(mv)
                    cur.add_move(x,mv);
                cerr<<"!"<<U.gsz(x)*U.gsz(y)<<"\n";
                break;*/
            }
            if(!csb) continue;
            auto sk1=info[1],md=info[2],x=info[3],mv=info[4];
            if(sk1!=-1)
                cur.add_move(sk1,md);
            if(mv)
                cur.add_move(x,mv);
        }
        else {
            bool upd=0;
            auto afb=add_freebie(cur);
            if(afb.fi.se>=last_se) {
                best=cur;
                last_se=afb.fi.se; upd=1;
            }
            reassign_bridge_id(); cur=best;
            nxt_rb=gen32()%3+1;
            while(gen32()%3) ++nxt_rb;
            ty=gen32()%3;
            if(upd) {
                auto added=afb;
                if(added.fi.fi>best_val) {
                    best_val=added.fi.fi;
                    best_arr=added.se;
                    best_op=best_arr.output();
                    last_gap=best_arr.gap();
                    #ifdef ENDLESS_TEST
                     {
                    /*
                    best_arr.clear_bridges();
                    cout<<best_arr.output()<<"\n";
                    best_arr.smart_greedy();
                    if(best_arr.validate())
                    cout<<best_arr.output()<<"\n";*/
                    cout<<best_op<<"\n";
                    }
                    #endif
                    cerr<<best_val<<"|"<<added.fi.se<<"+  "<<clock()*1./CLOCKS_PER_SEC<<"   G"<<last_gap<<"  S"<<og<<"\n";
                    best_arr.clear_bridges();
//                    cerr<<"  [RESET]"<<best_arr.val()<<"|"<<add_freebie_val(best_arr)<<"A\n";
                    best_arr.smart_greedy(50);
                    auto cv=best_arr.val().fi;
                    if(cv>best_val) {
                        best_val=cv; best_op=best_arr.output();
                        cerr<<"actual:"<<cv<<"\n";
                    }
//                    cerr<<"  [RESET]"<<best_arr.val()<<"|"<<add_freebie_val(best_arr)<<"B\n";
    //                cerr<<"val="<<best_arr.val()<<"\n";
    //                assert(best_arr.val()==best_val);
    //                best_arr.dbg();
                }
            }
            else
                afb.se.initufs();
            og=nxt_rb;
        }
//        system("pause");
    }
    puts(best_op.c_str());
    cerr<<"val="<<best_val<<"\n";
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:377:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  377 |     for(int i=0;i<2&&i<ve.size();++i) we[ve[i].se]=(3-i)*3;
      |                      ~^~~~~~~~~~

Judge Result