Submission #67648089

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

struct Command{char type;int idx;char dir;};
struct Timer{chrono::steady_clock::time_point st;Timer(){st=chrono::steady_clock::now();}double get(){return chrono::duration<double>(chrono::steady_clock::now()-st).count();}};
static int wallV[30][29];
static int wallH[29][30];
static uint64_t Zval[100][900];

constexpr size_t HASH_TABLE_SIZE = 1 << 21;
constexpr size_t HASH_TABLE_MASK = HASH_TABLE_SIZE - 1;
struct CustomHashTable {
    static constexpr uint64_t EMPTY_KEY = 0;
    uint64_t keys[HASH_TABLE_SIZE];
    CustomHashTable(){for(size_t i=0;i<HASH_TABLE_SIZE;i++)keys[i]=EMPTY_KEY;}
    bool find(uint64_t key){ if(key==EMPTY_KEY) key=1; size_t idx=(size_t)key&HASH_TABLE_MASK; while(keys[idx]!=EMPTY_KEY){ if(keys[idx]==key) return true; idx=(idx+1)&HASH_TABLE_MASK;} return false;}
    void insert(uint64_t key){ if(key==EMPTY_KEY) key=1; size_t idx=(size_t)key&HASH_TABLE_MASK; while(keys[idx]!=EMPTY_KEY){ if(keys[idx]==key) return; idx=(idx+1)&HASH_TABLE_MASK;} keys[idx]=key;}
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    mt19937_64 rng(12345);
    for(int k=0;k<100;k++)for(int i=0;i<900;i++)Zval[k][i]=rng();
    int Ntmp,K; if(!(cin>>Ntmp>>K)) return 0; int N=30;
    vector<int> si(K),sj(K),ti(K),tj(K);
    for(int k=0;k<K;k++)cin>>si[k]>>sj[k]>>ti[k]>>tj[k];
    for(int i=0;i<N;i++){string s;cin>>s;for(int j=0;j<N-1;j++)wallV[i][j]=s[j]-'0';}
    for(int i=0;i<N-1;i++){string s;cin>>s;for(int j=0;j<N;j++)wallH[i][j]=s[j]-'0';}

    vector<int> col_count(N,0), row_count(N,0);
    for(int k=0;k<K;k++){col_count[sj[k]]++;col_count[tj[k]]++;row_count[si[k]]++;row_count[ti[k]]++;}
    for(int j=0;j<N;j++){if(col_count[j]==0)for(int i=0;i<N-1;i++)wallH[i][j]=1;}
    for(int i=0;i<N;i++){if(row_count[i]==0)for(int j=0;j<N-1;j++)wallV[i][j]=1;}

    for(int i=0;i<N;i++){for(int j=0;j<N-1;j++)cout<<wallV[i][j];cout<<"\n";}
    for(int i=0;i<N-1;i++){for(int j=0;j<N;j++)cout<<wallH[i][j];cout<<"\n";}

    vector<double> dx(K),dy(K),wh(K,0),wv(K,0);
    for(int k=0;k<K;k++){
        dx[k]=ti[k]-si[k];dy[k]=tj[k]-sj[k];
        int ci=si[k],cj=sj[k],tii=ti[k],tjj=tj[k];
        int horizontal_walls=0,vertical_walls=0;
        if(cj<tjj)for(int c=cj;c<tjj;c++)if(wallV[ci][c])horizontal_walls++;
        else for(int c=tjj;c<cj;c++)if(wallV[ci][c])horizontal_walls++;
        if(ci<tii)for(int r=ci;r<tii;r++)if(wallH[r][cj])vertical_walls++;
        else for(int r=tii;r<ci;r++)if(wallH[r][cj])vertical_walls++;
        wh[k]=horizontal_walls;wv[k]=vertical_walls;
    }
    int num_cluster;
    if(K<=20)num_cluster=2;
    else if(K<=40)num_cluster=4;
    else num_cluster=min(20,max(5,K/5));
    vector<double> cx(num_cluster,0),cy(num_cluster,0),cx2(num_cluster,0),cy2(num_cluster,0);
    vector<double> cxd(num_cluster,0),cyd(num_cluster,0);
    vector<int> assignments(K,0);
    for(int k=0;k<K;k++){
        int idx=0;double best=1e18;double norm=sqrt(dx[k]*dx[k]+dy[k]*dy[k]);
        double ndx=(norm>0)?dx[k]/norm:0.0;double ndy=(norm>0)?dy[k]/norm:0.0;
        for(int c=0;c<num_cluster;c++){
            double dist=(dx[k]-cx[c])*(dx[k]-cx[c])+(dy[k]-cy[c])*(dy[k]-cy[c])+(wh[k]-cx2[c])*(wh[k]-cx2[c])+(wv[k]-cy2[c])*(wv[k]-cy2[c])+4*((ndx-cxd[c])*(ndx-cxd[c])+(ndy-cyd[c])*(ndy-cyd[c]));
            if(dist<best){best=dist;idx=c;}
        }assignments[k]=idx;
    }
    for(int iter=0;iter<20;iter++){
        vector<double> sumx(num_cluster,0),sumy(num_cluster,0),sumx2(num_cluster,0),sumy2(num_cluster,0);
        vector<double> sumdx(num_cluster,0),sumdy(num_cluster,0);vector<int> cnt(num_cluster,0);
        for(int k=0;k<K;k++){
            int idx=assignments[k];
            sumx[idx]+=dx[k];sumy[idx]+=dy[k];sumx2[idx]+=wh[k];sumy2[idx]+=wv[k];
            double norm=sqrt(dx[k]*dx[k]+dy[k]*dy[k]);
            double ndx=(norm>0)?dx[k]/norm:0.0;double ndy=(norm>0)?dy[k]/norm:0.0;
            sumdx[idx]+=ndx;sumdy[idx]+=ndy;cnt[idx]++;
        }
        for(int c=0;c<num_cluster;c++){
            if(cnt[c]){cx[c]=sumx[c]/cnt[c];cy[c]=sumy[c]/cnt[c];cx2[c]=sumx2[c]/cnt[c];cy2[c]=sumy2[c]/cnt[c];cxd[c]=sumdx[c]/cnt[c];cyd[c]=sumdy[c]/cnt[c];double nd=sqrt(cx[c]*cx[c]+cy[c]*cy[c]);if(nd>0){cxd[c]/=nd;cyd[c]/=nd;}else{cxd[c]=0;cyd[c]=0;}}
        }
        bool changed=false;
        for(int k=0;k<K;k++){
            double best=1e18;int idx=0;double norm=sqrt(dx[k]*dx[k]+dy[k]*dy[k]);
            double ndx=(norm>0)?dx[k]/norm:0.0;double ndy=(norm>0)?dy[k]/norm:0.0;
            for(int c=0;c<num_cluster;c++){
                double dist=(dx[k]-cx[c])*(dx[k]-cx[c])+(dy[k]-cy[c])*(dy[k]-cy[c])+(wh[k]-cx2[c])*(wh[k]-cx2[c])+(wv[k]-cy2[c])*(wv[k]-cy2[c])+4*((ndx-cxd[c])*(ndx-cxd[c])+(ndy-cyd[c])*(ndy-cyd[c]));
                if(dist<best){best=dist;idx=c;}
            }
            if(idx!=assignments[k]){assignments[k]=idx;changed=true;}
        }
        if(!changed)break;
    }
    vector<int> group=assignments;
    for(int k=0;k<K;k++){if(k)cout<<" ";cout<<group[k];}
    cout<<"\n";

    vector<pair<int,int>> pos(K);
    for(int k=0;k<K;k++)pos[k]={si[k],sj[k]};
    vector<int> board(900,-1);
    for(int k=0;k<K;k++)board[si[k]*30+sj[k]]=k;
    vector<vector<int>> inGroup(num_cluster);
    for(int k=0;k<K;k++)inGroup[group[k]].push_back(k);

    auto canMoveCell=[&](int cell,int dir)->bool{
        int r=cell/30,c=cell%30;
        if(dir==0){if(r==0||wallH[r-1][c])return false;}
        else if(dir==1){if(r==29||wallH[r][c])return false;}
        else if(dir==2){if(c==0||wallV[r][c-1])return false;}
        else{if(c==29||wallV[r][c])return false;}
        return true;
    };
    int deltaDir[4]={-30,30,-1,1};
    char dirChar[4]={'U','D','L','R'};

    auto applyGroupGlobal=[&](int g,char d){
        vector<int> ids=inGroup[g]; if(ids.empty())return;
        if(d=='U'||d=='L')sort(ids.begin(),ids.end(),[&](int a,int b){return (d=='U')?pos[a].first<pos[b].first:pos[a].second<pos[b].second;});
        else sort(ids.begin(),ids.end(),[&](int a,int b){return (d=='D')?pos[a].first>pos[b].first:pos[a].second>pos[b].second;});
        int dirIndex=(d=='U'?0:(d=='D'?1:(d=='L'?2:3)));
        for(int k:ids){
            int r=pos[k].first,c=pos[k].second;
            int cell=r*30+c;
            if(!canMoveCell(cell,dirIndex))continue;
            int nc=cell+deltaDir[dirIndex];
            if(board[nc]!=-1)continue;
            board[cell]=-1;board[nc]=k;pos[k]={nc/30,nc%30};
        }
    };

    vector<vector<int>> allDist(900,vector<int>(900,1<<30));
    for(int cell=0;cell<900;cell++){
        int r=cell/30;queue<int> q;
        vector<int> &dist=allDist[cell];
        dist[cell]=0;q.push(cell);
        while(!q.empty()){
            int cur=q.front();q.pop();
            int cd=dist[cur];
            for(int dir=0;dir<4;dir++){
                if(!canMoveCell(cur,dir))continue;
                int nxt=cur+deltaDir[dir];
                if(dist[nxt]>cd+1){dist[nxt]=cd+1;q.push(nxt);}
            }
        }
    }

    Timer timer;
    vector<Command> cmds;

    double total_time_budget=1.9;
    double time_per_group=total_time_budget/num_cluster;
    for(int g=0;g<num_cluster;g++){
        if(inGroup[g].empty())continue;
        double group_start_time=timer.get();
        vector<int> curPos;vector<int> members=inGroup[g];int msize=members.size();
        for(int ii=0;ii<msize;ii++){int rid=members[ii];curPos.push_back(pos[rid].first*30+pos[rid].second);}
        auto distForPos=[&](const vector<int>& p)->int{
            int s=0,m=0;
            for(int ii=0;ii<msize;ii++){int rid=members[ii];int cell=p[ii];int d=allDist[cell][ti[rid]*30+tj[rid]];s+=d;if(d>m)m=d;}
            return s+m/2;
        };
        int distGroup=distForPos(curPos);
        while(true){
            vector<char> fixedBoard(900,0);for(int k=0;k<K;k++){if(group[k]==g)continue;int cell=pos[k].first*30+pos[k].second;fixedBoard[cell]=1;}
            double elapsed=timer.get();double TIME_LIMIT=1.9;double minBeam,maxBeam;
            if(K<=20){minBeam=140.0;maxBeam=1400.0;}
            else if(K<=40){minBeam=120.0;maxBeam=1200.0;}
            else if(K<=60){minBeam=100.0;maxBeam=1000.0;}
            else if(K<=80){minBeam=90.0;maxBeam=900.0;}
            else{minBeam=80.0;maxBeam=800.0;}
            double t_ratio=max(0.0,min(1.0,elapsed/TIME_LIMIT));double baseBeamWidth=minBeam+(1.0-t_ratio)*(maxBeam-minBeam);
            double groupAvgDist=0.0;for(int ii=0;ii<msize;ii++){int rid=members[ii];int cell=curPos[ii];groupAvgDist+=allDist[cell][ti[rid]*30+tj[rid]];}
            groupAvgDist/=msize;double widthFactor=(1.0+((double)msize/K)*1.5);widthFactor*=(1.0+groupAvgDist/100.0);
            double beamWidth_d=baseBeamWidth*widthFactor;if(beamWidth_d>1.5*maxBeam)beamWidth_d=1.5*maxBeam;int beamWidth=(int)beamWidth_d;
            double elapsed_group=elapsed-group_start_time;double desired_elapsed_group=time_per_group*(g+1);double time_factor=desired_elapsed_group/max(elapsed_group,1e-9);
            if(time_factor<0.5)time_factor=0.5;else if(time_factor>1.5)time_factor=1.5;beamWidth=(int)(beamWidth*time_factor);
            struct Node{vector<int> p;int dist;vector<char> cmd;uint64_t h;double variance;double dirVariance;};
            auto calcHash=[&](const vector<int>& p)->uint64_t{uint64_t h=0;for(int ii=0;ii<msize;ii++){int rid=members[ii];h^=Zval[rid][p[ii]];}return h;};
            CustomHashTable visited;vector<Node> frontier;Node startnode;startnode.p=curPos;startnode.dist=distGroup;startnode.cmd.clear();startnode.h=calcHash(curPos);
            double sum=0.0,sumsq=0.0;for(int ii=0;ii<msize;ii++){int rid=members[ii];int cell=curPos[ii];int d=allDist[cell][ti[rid]*30+tj[rid]];sum+=d;sumsq+=d*d;}double mean=sum/msize;double var=sumsq/msize-mean*mean;startnode.variance=var;
            double sumdx=0.0,sumdy=0.0;vector<double> rdx(msize),rdy(msize);for(int ii=0;ii<msize;ii++){int rid=members[ii];int cell=curPos[ii];int rx=cell/30,ry=cell%30;double dxv=ti[rid]-rx,dyv=tj[rid]-ry;rdx[ii]=dxv;rdy[ii]=dyv;sumdx+=dxv;sumdy+=dyv;}double avgdx=sumdx/msize,avgdy=sumdy/msize;double sumvar=0.0;for(int ii=0;ii<msize;ii++){double ddx=rdx[ii]-avgdx,ddy=rdy[ii]-avgdy;sumvar+=ddx*ddx+ddy*ddy;}startnode.dirVariance=sumvar/msize;
            frontier.push_back(startnode);visited.insert(startnode.h);int bestDist=distGroup;vector<char> bestCmd;
            int depthLimit=min(80,max(10,distGroup/2+5));
            for(int depth=0;depth<depthLimit;depth++){
                vector<Node> nextList;
                for(auto &nd:frontier){
                    double curScore=nd.dist+(int)nd.cmd.size();if(curScore<bestDist+(int)bestCmd.size()){bestDist=nd.dist;bestCmd=nd.cmd;}
                    for(int di=0;di<4;di++){
                        char dch=dirChar[di];vector<int> np=nd.p;static char occ[900];memset(occ,0,sizeof(occ));
                        for(int ii=0;ii<msize;ii++)occ[np[ii]]=1;vector<int> order(msize);for(int ii=0;ii<msize;ii++)order[ii]=ii;
                        if(dch=='U')sort(order.begin(),order.end(),[&](int a,int b){return np[a]<np[b];});
                        else if(dch=='D')sort(order.begin(),order.end(),[&](int a,int b){return np[a]>np[b];});
                        else if(dch=='L')sort(order.begin(),order.end(),[&](int a,int b){return np[a]<np[b];});
                        else sort(order.begin(),order.end(),[&](int a,int b){return np[a]>np[b];});
                        bool movedAny=false;for(int idxOrd:order){int cell=np[idxOrd];if(!canMoveCell(cell,di))continue;int nxt=cell+deltaDir[di];occ[cell]=0;if(!fixedBoard[nxt]&&!occ[nxt]){occ[nxt]=1;np[idxOrd]=nxt;movedAny=true;}else occ[cell]=1;}
                        if(!movedAny)continue;uint64_t nh=calcHash(np);if(visited.find(nh))continue;visited.insert(nh);Node nn;nn.p.swap(np);nn.dist=distForPos(nn.p);nn.cmd=nd.cmd;nn.cmd.push_back(dch);nn.h=nh;
                        double sum=0.0,sumsq=0.0;for(int ii=0;ii<msize;ii++){int rid=members[ii];int cell=nn.p[ii];int d=allDist[cell][ti[rid]*30+tj[rid]];sum+=d;sumsq+=d*d;}double mean=sum/msize;double var=sumsq/msize-mean*mean;nn.variance=var;
                        double sumdx=0.0,sumdy=0.0;vector<double> rdx(msize),rdy(msize);for(int ii=0;ii<msize;ii++){int rid=members[ii];int cell=nn.p[ii];int rx=cell/30,ry=cell%30;double dxv=ti[rid]-rx,dyv=tj[rid]-ry;rdx[ii]=dxv;rdy[ii]=dyv;sumdx+=dxv;sumdy+=dyv;}double avgdx=sumdx/msize,avgdy=sumdy/msize;double sumvar=0.0;for(int ii=0;ii<msize;ii++){double ddx=rdx[ii]-avgdx,ddy=rdy[ii]-avgdy;sumvar+=ddx*ddx+ddy*ddy;}nn.dirVariance=sumvar/msize;
                        nextList.push_back(std::move(nn));
                    }
                }
                if(nextList.empty())break;
                sort(nextList.begin(),nextList.end(),[&](const Node&a,const Node&b){double aScore=a.dist+(int)a.cmd.size()+a.variance+4.5*a.dirVariance;double bScore=b.dist+(int)b.cmd.size()+b.variance+4.5*b.dirVariance;return aScore<bScore;});
                if((int)nextList.size()>beamWidth)nextList.resize(beamWidth);
                frontier.swap(nextList);
            }
            if(bestCmd.size()>0&&bestDist<distGroup){
                for(char d:bestCmd){cmds.push_back({'g',g,d});applyGroupGlobal(g,d);}
                curPos.clear();for(int ii=0;ii<msize;ii++){int rid=members[ii];curPos.push_back(pos[rid].first*30+pos[rid].second);}distGroup=distForPos(curPos);groupAvgDist=0.0;for(int ii=0;ii<msize;ii++){int rid=members[ii];int cell=curPos[ii];groupAvgDist+=allDist[cell][ti[rid]*30+tj[rid]];}groupAvgDist/=msize;widthFactor=(1.0+((double)msize/K)*1.5);widthFactor*=(1.0+groupAvgDist/100.0);beamWidth_d=baseBeamWidth*widthFactor;if(beamWidth_d>1.5*maxBeam)beamWidth_d=1.5*maxBeam;beamWidth=(int)beamWidth_d;elapsed=timer.get();elapsed_group=elapsed-group_start_time;desired_elapsed_group=time_per_group*(g+1);time_factor=desired_elapsed_group/max(elapsed_group,1e-9);if(time_factor<0.5)time_factor=0.5;else if(time_factor>1.5)time_factor=1.5;beamWidth=(int)(beamWidth*time_factor);
            }else break;
            if(timer.get()>1.7)break;
        }
        if(timer.get()>1.85)break;
    }

    auto moveSingle=[&](int k,int dirIndex){
        int r=pos[k].first,c=pos[k].second;int cell=r*30+c;
        if(!canMoveCell(cell,dirIndex))return;int nxt=cell+deltaDir[dirIndex];if(board[nxt]!=-1)return;
        board[cell]=-1;board[nxt]=k;pos[k]={nxt/30,nxt%30};
    };

    auto findPath=[&](pair<int,int> s,pair<int,int> t)->vector<char>{
        struct NodeP{int pos;int g;int f;NodeP(int pos,int g,int f):pos(pos),g(g),f(f){}bool operator<(const NodeP& other)const{return f>other.f;}};
        vector<int> g_score(900,1<<30);vector<int> came_from(900,-1);vector<int> pdir(900,-1);priority_queue<NodeP> open_set;
        auto heuristic=[&](int a,int b){int ar=a/30,ac=a%30,br=b/30,bc=b%30;return abs(ar-br)+abs(ac-bc);};
        int start=s.first*30+s.second;int goal=t.first*30+t.second;g_score[start]=0;open_set.push(NodeP(start,0,heuristic(start,goal)));
        while(!open_set.empty()){NodeP current=open_set.top();open_set.pop();if(current.pos==goal)break;int cur=current.pos;int cd=current.g;
            for(int dir=0;dir<4;dir++){if(!canMoveCell(cur,dir))continue;int nxt=cur+deltaDir[dir];int tentative_g=cd+1;if(tentative_g<g_score[nxt]&&board[nxt]==-1){came_from[nxt]=cur;pdir[nxt]=dir;g_score[nxt]=tentative_g;int fscore=tentative_g+heuristic(nxt,goal);open_set.push(NodeP(nxt,tentative_g,fscore));}}}
        vector<char> path;if(g_score[goal]==(1<<30))return path;int cur=goal;while(cur!=start){int dir=pdir[cur];path.push_back(dirChar[dir]);cur=came_from[cur];}reverse(path.begin(),path.end());return path;
    };

    // ---- New: improved post-processing
    auto planSmallGroup=[&](const vector<int>& subset)->vector<pair<int,char>>{
        int m=subset.size();vector<pair<int,char>> res;if(m==0)return res;
        static bool occFixed[900];
        fill(occFixed,occFixed+900,false);
        for(int k=0;k<K;k++){
            bool inside=false;for(int id:subset)if(id==k){inside=true;break;}
            if(!inside){int cell=pos[k].first*30+pos[k].second;occFixed[cell]=true;}
        }
        short start[3],goal[3];for(int i=0;i<m;i++){int id=subset[i];start[i]=pos[id].first*30+pos[id].second;goal[i]=ti[id]*30+tj[id];}
        bool ok=true;for(int i=0;i<m;i++)if(start[i]!=goal[i])ok=false;if(ok)return res;
        struct Node{short cell[3];int parent;char dir;char who;};
        auto encode=[&](short*cell)->uint64_t{uint64_t key=0,base=1;for(int i=0;i<m;i++){key+=base*(uint64_t)cell[i];base*=900;}return key;};
        auto heuristic=[&](short*cell)->int{int sum=0;for(int i=0;i<m;i++){int r=cell[i]/30,c=cell[i]%30;sum+=abs(r-ti[subset[i]])+abs(c-tj[subset[i]]);}return sum;};
        unordered_map<uint64_t,int> best;best.reserve(20000);
        vector<Node> nodes;nodes.reserve(20000);
        Node st;for(int i=0;i<m;i++)st.cell[i]=start[i];st.parent=-1;st.dir='?';st.who=-1;nodes.push_back(st);
        struct PQItem{int f,g,idx;uint64_t key;bool operator<(const PQItem&o)const{return f>o.f;}};
        priority_queue<PQItem>pq;
        uint64_t key0=encode(start);best[key0]=0;pq.push({heuristic(start),0,0,key0});
        int limitState=20000;
        while(!pq.empty()&&(int)nodes.size()<limitState){
            auto cur=pq.top();pq.pop();if(cur.g!=best[cur.key])continue;
            Node nd=nodes[cur.idx];short cell[3];for(int i=0;i<m;i++)cell[i]=nd.cell[i];
            int hcur=heuristic(cell);if(hcur==0){vector<pair<int,char>> path;int idx=cur.idx;while(nodes[idx].parent!=-1){path.push_back({subset[nodes[idx].who],nodes[idx].dir});idx=nodes[idx].parent;}reverse(path.begin(),path.end());return path;}
            for(int who=0;who<m;who++){
                int cellx=cell[who];for(int d=0;d<4;d++){
                    if(!canMoveCell(cellx,d))continue;int nxt=cellx+deltaDir[d];if(occFixed[nxt])continue;
                    bool clash=false;for(int j=0;j<m;j++)if(j!=who&&cell[j]==nxt){clash=true;break;}if(clash)continue;
                    short newc[3];for(int j=0;j<m;j++)newc[j]=cell[j];newc[who]=nxt;uint64_t kx=encode(newc);
                    int ng=cur.g+1;if(best.find(kx)==best.end()||ng<best[kx]){best[kx]=ng;Node nn;for(int j=0;j<m;j++)nn.cell[j]=newc[j];nn.parent=cur.idx;nn.dir=dirChar[d];nn.who=who;int nf=ng+heuristic(newc);nodes.push_back(nn);pq.push({nf,ng,(int)nodes.size()-1,kx});}
                }
            }
        }
        return res;
    };

    // attempt improved search for some time
    while(timer.get()<1.65){
        vector<int> unsolved;
        for(int k=0;k<K;k++)if(!(pos[k].first==ti[k]&&pos[k].second==tj[k]))unsolved.push_back(k);
        if(unsolved.empty())break;
        bool progressed=false;
        for(int base=0;base<(int)unsolved.size() && !progressed;base++){
            vector<int> cand;cand.push_back(unsolved[base]);
            vector<pair<int,int>> dist;for(int j=0;j<(int)unsolved.size();j++)if(j!=base){int a=unsolved[base];int b=unsolved[j];int d=abs(pos[a].first-pos[b].first)+abs(pos[a].second-pos[b].second);dist.push_back({d,unsolved[j]});}
            sort(dist.begin(),dist.end());for(int x=0;x<2&&x<(int)dist.size();x++)cand.push_back(dist[x].second);
            auto plan=planSmallGroup(cand);
            if(!plan.empty()&&plan.size()<60){
                for(auto &mv:plan){int rid=mv.first;char dc=mv.second;int di=(dc=='U'?0:(dc=='D'?1:(dc=='L'?2:3)));cmds.push_back({'i',rid,dc});moveSingle(rid,di);}
                progressed=true;
            }
        }
        if(!progressed)break;
    }

    // original final individual handling
    vector<bool> fin(K,false);int rem=K;
    for(int k=0;k<K;k++)if(pos[k].first==ti[k]&&pos[k].second==tj[k]){fin[k]=true;rem--;}
    while(rem>0){
        bool prog=false;
        for(int k=0;k<K;k++){
            if(fin[k])continue;
            if(pos[k].first==ti[k]&&pos[k].second==tj[k]){fin[k]=true;rem--;continue;}
            int targetCell=ti[k]*30+tj[k];
            int occ=board[targetCell];
            if(occ!=-1&&occ!=k){
                int r=pos[occ].first,c=pos[occ].second;int bestDir=-1;int bestDist=1<<30;int cell=r*30+c;
                for(int dir=0;dir<4;dir++){if(!canMoveCell(cell,dir))continue;int nxt=cell+deltaDir[dir];if(board[nxt]==-1){int d=allDist[nxt][ti[occ]*30+tj[occ]];if(d<bestDist){bestDist=d;bestDir=dir;}}}
                if(bestDir!=-1){cmds.push_back({'i',occ,dirChar[bestDir]});moveSingle(occ,bestDir);}prog=true;
            }
            vector<char> path=findPath({pos[k].first,pos[k].second},{ti[k],tj[k]});if(path.empty())continue;
            for(char dc:path){int di=(dc=='U'?0:(dc=='D'?1:(dc=='L'?2:3)));cmds.push_back({'i',k,dc});moveSingle(k,di);}
            if(pos[k].first==ti[k]&&pos[k].second==tj[k]){fin[k]=true;rem--;}
            prog=true;
        }
        if(!prog)break;
    }

    // Compression of consecutive individual moves of same group and direction
    vector<Command> finalCmds;
    vector<pair<int,int>> simPos(K);
    vector<int> simBoard(900,-1);
    for(int k=0;k<K;k++){simPos[k]={si[k],sj[k]};simBoard[si[k]*30+sj[k]]=k;}
    auto moveSingleLocal=[&](vector<pair<int,int>>&p,vector<int>&b,int rid,int dirI){
        int r=p[rid].first,c=p[rid].second;int cell=r*30+c;
        if(!canMoveCell(cell,dirI))return;
        int nxt=cell+deltaDir[dirI];
        if(b[nxt]!=-1)return;
        b[cell]=-1;b[nxt]=rid;p[rid]={nxt/30,nxt%30};
    };
    auto applyGroupLocal=[&](vector<pair<int,int>>&p,vector<int>&b,const vector<int>&ids,char d){
        vector<int> loc=ids;if(d=='U'||d=='L')sort(loc.begin(),loc.end(),[&](int a,int b_){return (d=='U')?p[a].first<p[b_].first:p[a].second<p[b_].second;});
        else sort(loc.begin(),loc.end(),[&](int a,int b_){return (d=='D')?p[a].first>p[b_].first:p[a].second>p[b_].second;});
        int dirIndex=(d=='U'?0:(d=='D'?1:(d=='L'?2:3)));
        for(int k:loc){
            int r=p[k].first,c=p[k].second;int cell=r*30+c;
            if(!canMoveCell(cell,dirIndex))continue;int nc=cell+deltaDir[dirIndex];
            if(b[nc]!=-1)continue;b[cell]=-1;b[nc]=k;p[k]={nc/30,nc%30};
        }
    };

    for(size_t p=0;p<cmds.size();){
        Command &c=cmds[p];
        if(c.type=='i'){
            int g=group[c.idx];char d=c.dir;size_t q=p;unordered_set<int> rs;
            while(q<cmds.size()&&cmds[q].type=='i'&&group[cmds[q].idx]==g&&cmds[q].dir==d&&!rs.count(cmds[q].idx)){rs.insert(cmds[q].idx);q++;}
            if(rs.size()>1){
                auto bA=simBoard;auto pA=simPos;
                for(size_t t=p;t<q;t++){int rid=cmds[t].idx;int di=(d=='U'?0:(d=='D'?1:(d=='L'?2:3)));moveSingleLocal(pA,bA,rid,di);}
                auto bB=simBoard;auto pB=simPos;applyGroupLocal(pB,bB,inGroup[g],d);
                if(bA==bB){finalCmds.push_back({'g',g,d});simBoard.swap(bA);simPos.swap(pA);p=q;continue;}
            }
        }
        // normal command
        finalCmds.push_back(c);
        if(c.type=='g'){applyGroupLocal(simPos,simBoard,inGroup[c.idx],c.dir);}
        else{int di=(c.dir=='U'?0:(c.dir=='D'?1:(c.dir=='L'?2:3)));moveSingleLocal(simPos,simBoard,c.idx,di);}
        p++;
    }

    for(auto &c:finalCmds)cout<<c.type<<" "<<c.idx<<" "<<c.dir<<"\n";
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:44:11: warning: suggest explicit braces to avoid ambiguous ‘else’ [-Wdangling-else]
   44 |         if(cj<tjj)for(int c=cj;c<tjj;c++)if(wallV[ci][c])horizontal_walls++;
      |           ^
Main.cpp:46:11: warning: suggest explicit braces to avoid ambiguous ‘else’ [-Wdangling-else]
   46 |         if(ci<tii)for(int r=ci;r<tii;r++)if(wallH[r][cj])vertical_walls++;
      |           ^
Main.cpp:129:13: warning: unused variable ‘r’ [-Wunused-variable]
  129 |         int r=cell/30;queue<int> q;
      |             ^
Main.cpp:186:25: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
  186 |                         for(int ii=0;ii<msize;ii++)occ[np[ii]]=1;vector<int> order(msize);for(int ii=0;ii<msize;ii++)order[ii]=ii;
      |                         ^~~
Main.cpp:186:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for’
  186 |                         for(int ii=0;ii<msize;ii++)occ[np[ii]]=1;vector<int> order(msize);for(int ii=0;ii<msize;ii++)order[ii]=ii;
      |                                                                  ^~~~~~
Main.cpp:192:25: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  192 |                         if(!movedAny)continue;uint64_t nh=calcHash(np);if(visited.find(nh))continue;visited.insert(nh);Node nn;nn.p.swap(np);nn.dist=distForPos(nn.p);nn.cmd=nd.cmd;nn.cmd.push_back(dch);nn.h=nh;
      |                         ^~
Main.cpp:192:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  192 |                         if(!movedAny)continue;uint64_t nh=calcHash(np);if(visited.find(nh))continue;visited.insert(nh);Node nn;nn.p.swap(np);nn.dist=distForPos(nn.p);nn.cmd=nd.cmd;nn.cmd.push_back(dch);nn.h=nh;
      |                                               ^~~~~~~~
Main.cpp: In lambda function:
Main.cpp:214:9: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  214 |         if(!canMoveCell(cell,dirIndex))return;int nxt=cell+deltaDir[dirIndex];if(board[nxt]!=-1)return;
      |         ^~
Main.cpp:214:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  214 |         if(!canMoveCell(cell,dirIndex))return;int nxt=cell+deltaDir[dirIndex];if(board[nxt]!=-1)return;
      |                                               ^~~
Main.cpp: In lambda function:
Main.cpp:255:21: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  255 |                     if(!canMoveCell(cellx,d))continue;int nxt=cellx+deltaDir[d];if(occFixed[nxt])continue;
      |                     ^~
Main.cpp:255:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  255 |                     if(!canMoveCell(cellx,d))continue;int nxt=cellx+deltaDir[d];if(occFixed[nxt])continue;
      |                                                       ^~~
Main.cpp: In lambda function:
Main.cpp:325:13: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  325 |             if(!canMoveCell(cell,dirIndex))continue;int nc=cell+deltaDir[dirIndex];
      |             ^~
Main.cpp:325:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  325 |             if(!canMoveCell(cell,dirIndex))continue;int nc=cell+deltaDir[dirIndex];
      |                                                     ^~~
Main.cpp:326:13: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  326 |             if(b[nc]!=-1)continue;b[cell]=-1;b[nc]=k;p[k]={nc/30,nc%30};
      |             ^~
Main.cpp:326:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  326 |             if(b[nc]!=-1)continue;b[cell]=-1;b[nc]=k;p[k]={nc/30,nc%30};
      |                                   ^

Judge Result