[일반] 오픈ai가 마지막에 제출한 코드 (스압)

[익명(cleep00001)]

#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;

}

[ㅇㅇ 1(119.192)]

정말 고마어요

[ㅇㅇ 2(211.106)]

가독성 ㅅㅂ 색깔입혀서 다시떠와

[익명(cleep00001)]

유식이한테 잘좀 만들어달라그래..

[초존도초(htr3c654r6ft)]

Artifex를 쓰세요!

[ㅇㅇ 3(183.98)]

생각보단 짧네