Submission #18021

#	Time	Username	Problem	Language	Result	Execution time	Memory
18021		gs13068	여왕벌 (KOI15_queen)	C++98	101 / 100	2238 ms	40076 KiB

Main

#include<cstdio>
#include<vector>
 
char a[707][707][33];
int r[707][707];
 
int val(const char,const int,const int,const int);
void cal(const int,const int,const int,const int,const int,const int,const std::vector<int>&,std::vector<int>&);
void dnc(const int,const int,const int,const int,const std::vector<int>&,std::vector<int>&);
 
int main()
{
    std::vector<int> in,out;
    int i,j,n,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<n;i++)for(j=1;j<n;j++)scanf("%s",a[i][j]);
    in.resize(4*(n+1)*(n+1));
    out.resize(4*(n+1)*(n+1));
    while(m--)
    {
        scanf("%d%d%*s",&i,&j);
        i++;
        j+=i;
        in[i*2*(n+1)+j]++;
    }
    dnc(0,0,n+1,n+1,in,out);
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)printf("%d ",r[i][j]+1);
        puts("");
    }
}
 
int val(const char c,const int l,const int d,const int u)
{
    return c=='L'?l:c=='D'?d:u;
}
 
void cal(const int sx,const int sy,const int ex,const int ey,const int of,const int sz,const std::vector<int> &in,std::vector<int> &out)
{
    int i,x,y,z,tsz;
    std::vector<int> tin,tout;
    tsz=ex+ey-sx-sy;
    tin.resize(tsz*tsz);
    tout.resize(tsz*tsz);
    for(i=0;i<sz*sz;i++)if(in[i])
    {
        x=std::min(std::max(out[i]/sz-of,0),tsz-1);
        y=std::min(std::max(out[i]%sz-of,0),tsz-1);
        tin[x*tsz+y]+=in[i];
    }
    dnc(sx,sy,ex,ey,tin,tout);
    for(i=0;i<sz*sz;i++)if(in[i])
    {
        x=out[i]/sz-of;
        y=out[i]%sz-of;
        if(x>=0&&x<tsz)
        {
            if(y>=0&&y<tsz)
            {
                z=tout[x*tsz+y];
                x=z/tsz;
                y=z%tsz;
            }
            else x=tout[x*tsz+tsz-1]/tsz;
        }
        else if(y>=0&&y<tsz)y=tout[y]%tsz;
        out[i]=(x+of)*sz+(y+of);
    }
}
 
void dnc(const int sx,const int sy,const int ex,const int ey,const std::vector<int> &in,std::vector<int> &out)
{
    int i,sz;
    sz=ex+ey-sx-sy;
    for(i=0;i<sz*sz;i++)out[i]=i;
    if(ex-sx<2||ey-sy<2)return;
    if(ex-sx==2&&ey-sy==2)
    {
        int x,y,z;
        for(i=0;i<sz*sz;i++)if(in[i])
        {
            x=(i<4)+((i&3)<1);
            y=(i<8)+((i&3)<2);
            z=(i<12)+((i&3)<3);
            r[sx][sy]+=in[i]*y;
            y=val(a[sx+1][sy+1][x*9+y*3+z],x,y,z);
            out[i]=(((x<1)+(y<1)+(z<1))<<2)|((x<2)+(y<2)+(z<2));
        }
        return;
    }
    int tx,ty;
    std::vector<int> tin,tout;
    tx=(sx+ex)/2;
    ty=(sy+ey)/2;
    sz=ex+ey-sx-sy;
 
    cal(sx,sy,tx+1,ty+1,ex-tx-1,sz,in,out);
    cal(sx,ty,tx+1,ey,ex+ty-tx-sy-1,sz,in,out);
    cal(tx,sy,ex,ty+1,0,sz,in,out);
    cal(tx,ty,ex,ey,ty-sy,sz,in,out);
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 34 / 34
• Subtask 4: 32 / 32
• Subtask 5: 1 / 1