제출 #1307922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307922		exoworldgd	이주 (IOI25_migrations)	C++20	0 / 100	35 ms	1112 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
using ll=long long;
vector<tuple<int,int,int,int,bool>>ph;
int n,p1,p2,q1,q2,q3,r1,r2,r3,lu,lv,pr;
vector<int>cp,cq,g[10005];
pair<int,int>dl;
int pb(int m){
    int bb=1,bf=1e9,lm=2*cbrt(m+1)+2;
    for(int b=1,f;b<=lm;b++)f=(m+1+b-1)/b+((b*b-1+3)/4)-1,f<bf?(bf=f,bb=b):0;
    return bb;
}
int pf(int m){
    int bb=1,bf=1e9,lm=2*cbrt(m+1)+2;
    for(int b=1,st,f;b<=lm;b++)st=b*(b+1)/2,f=(m+1+b-1)/b+((st-1+3)/4)-1,f<bf?(bf=f,bb=b):0;
    return bb;
}
void calc(){
    for(int i=4;i<n-3;i++){
        ph.clear();
        int m=i-1,ps=i-1;
        bool fr=1;
        while(ps<n-3&&ph.size()<5){
            int b=fr?pf(m):pb(m),k=fr?((b*(b+1)/2-1+3)/4):((b*b-1+3)/4);
            ph.push_back(make_tuple(m,b,k,ps,fr)),m=(m+b-1)/b+k-1,ps+=k,fr=0;
        }
        reverse(ph.begin(),ph.end());
        if(ps==n-3&&ph.size()==5&&m<=4)break;
    }
}
vector<int>sl(const vector<int>&c,int bu,int b){int s=bu*b,e=min((int)c.size(),s+b);return vector<int>(c.begin()+s,c.begin()+e);}
int bf(int sr){
    vector<int>d(n,-1);
    queue<int>q;
    d[sr]=0,q.push(sr);
    for(int u;q.size();){
		u=q.front(),q.pop();	
		for(int v:g[u])d[v]<0?(d[v]=d[u]+1,q.push(v),0):0;
	}
    return max_element(d.begin(),d.end())-d.begin();
}
pair<int,int>dm(){int u=bf(0),v=bf(u);return{u,v};}
bool sm(pair<int,int>a,pair<int,int>b){
    a.first>a.second?swap(a.first,a.second),0:0,b.first>b.second?swap(b.first,b.second),0:0;
    return a==b;
}
int send_message(int N,int i,int p){
    if(N<=9){
        if(i==1){for(int j=0;j<N;j++)g[j].clear();lu=0,lv=1;}
        g[i].push_back(p),g[p].push_back(i);
        if(i>=2){
            n=N;
            auto[u,v]=dm();
            u>v?swap(u,v),0:0;
            int ms=u==lu&&v==lv?0:(v^lv&&u==lu?1:2);
            lu=u,lv=v;
            return ms;
        }
        return 0;
    }
    if(i==1){n=N,calc(),cp={0},cq={0},dl={-1,-1},pr=0;for(int j=0;j<N;j++)g[j].clear();}
    g[i].push_back(p),g[p].push_back(i);
    i<n-3?(cp.push_back(i),cq.push_back(i),0):0;
    if(i==get<3>(ph.back())){
        auto[u,v]=dm();
        auto[m,b,k,st,tr]=ph.back();
        find(cp.begin(),cp.end(),u)==cp.end()||find(cq.begin(),cq.end(),v)==cq.end()?swap(u,v),0:0;
        int iu=find(cp.begin(),cp.end(),u)-cp.begin(),iv=find(cq.begin(),cq.end(),v)-cq.begin(),bs=ceil((double)m/b),bu=iu/bs,bv=iv/bs;
        cp=sl(cp,bu,bs),cq=sl(cq,bv,bs);
        if(tr){
            u>v?(swap(u,v),swap(cp,cq),swap(bu,bv),0):0;
            int ix=0;
            for(int x=0;x<bu;x++)ix+=b-x;
            ix+=bv-bu,ix>=0?dl={i+(ix-1)/4,((ix-1)%4)+1},0:0;
        }else{int cl=bu*b+bv;cl?dl={i+(cl-1)/4,((cl-1)%4)+1},0:0;}
        ph.pop_back();
    }
    if(i==dl.first)return dl.second;
    if(i==n-3){
        while(cp.size()<4)cp.push_back(0);
        while(cq.size()<4)cq.push_back(0);
        vector<pair<int,int>>cd={{cp[0],cq[0]},{cp[0],cq[1]},{cp[0],cq[2]},{cp[1],cq[0]},{cp[1],cq[1]},{cp[0],cq[3]},{cp[0],i},{cp[1],cq[2]},{cp[1],cq[3]},{cp[1],i},{cp[2],cq[0]},{cp[2],cq[1]},{cp[3],cq[0]},{cp[3],cq[1]},{i,cq[0]},{cp[2],cq[2]},{cp[2],cq[3]},{cp[2],i},{cp[3],cq[3]},{cp[3],i},{cp[3],cq[2]},{i,cq[1]},{i,cq[2]},{i,cq[3]}};
        auto[u,v]=dm();
        find(cd.begin(),cd.end(),make_pair(u,v))==cd.end()?swap(u,v),0:0;
        return pr=(find(cd.begin(),cd.end(),make_pair(u,v))-cd.begin())/5;
    }
    if(i==n-2){
        int a1=cp[0],a2=cp[1],a3=cp[2],a4=cp[3],b1=cq[0],b2=cq[1],b3=cq[2],b4=cq[3];
        !pr?(p1=a1,p2=a2,q1=b1,q2=b2,q3=b3):pr==1?(p1=a2,p2=a1,q1=i-1,q2=b4,q3=b3):pr==2?(p1=b1,p2=b2,q1=a3,q2=a4,q3=i-1):pr==3?(p1=a3,p2=a4,q1=i-1,q2=b4,q3=b3):(p1=i-1,p2=a4,q1=b2,q2=b3,q3=b4);
        vector<pair<int,int>>cd={{p1,q1},{p2,q1},{p1,q2},{p2,q2},{p1,q3},{i,q3},{i,q1},{i,q2},{p1,i},{p2,i}};
        auto[u,v]=dm();
        find(cd.begin(),cd.end(),make_pair(u,v))==cd.end()?swap(u,v),0:0;
        return pr=(find(cd.begin(),cd.end(),make_pair(u,v))-cd.begin())/2;
    }
    if(i==n-1){
        pr==0?(r3=q1,r2=p1,r1=p2):pr==1?(r3=q2,r2=p1,r1=p2):pr==2?(r3=q3,r2=p1,r1=n-2):pr==3?(r3=n-2,r2=q1,r1=q2):(r3=n-2,r2=p1,r1=p2);
        auto[u,v]=dm();
        return sm({u,v},{r1,r3})?0:sm({u,v},{r2,r3})?1:sm({u,v},{r1,i})?2:sm({u,v},{r2,i})?3:4;
    }
    return 0;
}
pair<int,int>longest_path(vector<int>S){
    int N=S.size(),ps=0;
    n=N,pr=0;
    if(N<=9){
        int u=0,v=1;
        for(int i=1;i<N;i++)S[i]==1?v=i:(S[i]==2?(u=v,v=i):0);
        return{u,v};
    }
    cp.clear(),cq.clear(),calc();
    while(ph.size()){
        auto[m,b,k,st,tr]=ph.back();
        while(ps^st+1)cp.push_back(ps),cq.push_back(ps),ps++;
        int c=0,mg=-1;
        for(int i=ps-1;i<ps+k-1;i++)S[i]?mg=S[i]:c++;
        int cl=mg==-1?0:c*4+mg,bu=0,bv=0,bs=ceil((double)m/b);
        if(tr){
            cl++;
            for(int u=0;u<b;u++){
                int rw=b-u;
                if(cl<=rw){bu=u,bv=u+cl-1;break;}
                cl-=rw;
            }
        }else bu=cl/b,bv=cl%b;
        cp=sl(cp,bu,bs),cq=sl(cq,bv,bs);
        for(int i=ps;i<ps+k-1;i++)cp.push_back(i),cq.push_back(i);
        ps+=k-1,ph.pop_back();
    }
    while(cp.size()<4)cp.push_back(0);
    while(cq.size()<4)cq.push_back(0);
    int a1=cp[0],a2=cp[1],a3=cp[2],a4=cp[3],b1=cq[0],b2=cq[1],b3=cq[2],b4=cq[3];
    !S[N-3]?(p1=a1,p2=a2,q1=b1,q2=b2,q3=b3):S[N-3]==1?(p1=a2,p2=a1,q1=N-3,q2=b4,q3=b3):S[N-3]==2?(p1=b1,p2=b2,q1=a3,q2=a4,q3=N-3):S[N-3]==3?(p1=a3,p2=a4,q1=N-3,q2=b4,q3=b3):(p1=N-3,p2=a4,q1=b2,q2=b3,q3=b4),!S[N-2]?(r3=q1,r2=p1,r1=p2):S[N-2]==1?(r3=q2,r2=p1,r1=p2):S[N-2]==2?(r3=q3,r2=p1,r1=N-2):S[N-2]==3?(r3=N-2,r2=q1,r1=q2):(r3=N-2,r2=p1,r1=p2);
    return !S[N-1]?make_pair(r1,r3):S[N-1]==1?make_pair(r2,r3):S[N-1]==2?make_pair(r1,N-1):S[N-1]==3?make_pair(r2,N-1):make_pair(r3,N-1);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 30
• Subtask 2: 0 / 70