oj.uz

답안 #18021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18021 2016-01-18T11:27:08 Z gs13068 여왕벌 (KOI15_queen) C++
101 / 100
 2238 ms 40076 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 19640 KB Output is correct
2 Correct 0 ms 19640 KB Output is correct
3 Correct 11 ms 19960 KB Output is correct
4 Correct 13 ms 19960 KB Output is correct
5 Correct 120 ms 23368 KB Output is correct
6 Correct 99 ms 23368 KB Output is correct
7 Correct 115 ms 23368 KB Output is correct
8 Correct 259 ms 30112 KB Output is correct
9 Correct 269 ms 30112 KB Output is correct
10 Correct 625 ms 40076 KB Output is correct
11 Correct 653 ms 40076 KB Output is correct
12 Correct 606 ms 40076 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 19640 KB Output is correct
2 Correct 128 ms 23368 KB Output is correct
3 Correct 220 ms 26252 KB Output is correct
4 Correct 701 ms 40076 KB Output is correct
5 Correct 687 ms 40076 KB Output is correct
6 Correct 676 ms 40076 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 19640 KB Output is correct
2 Correct 24 ms 19960 KB Output is correct
3 Correct 338 ms 30112 KB Output is correct
4 Correct 761 ms 40076 KB Output is correct
5 Correct 757 ms 40076 KB Output is correct
6 Correct 755 ms 40076 KB Output is correct
7 Correct 794 ms 40076 KB Output is correct
8 Correct 859 ms 40076 KB Output is correct
9 Correct 850 ms 40076 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 673 ms 30112 KB Output is correct
2 Correct 768 ms 30112 KB Output is correct
3 Correct 2238 ms 40076 KB Output is correct
4 Correct 1183 ms 40076 KB Output is correct
5 Correct 1232 ms 40076 KB Output is correct
6 Correct 1208 ms 40076 KB Output is correct
7 Correct 1209 ms 40076 KB Output is correct
8 Correct 1187 ms 40076 KB Output is correct
9 Correct 1323 ms 40076 KB Output is correct
10 Correct 1325 ms 40076 KB Output is correct

Subtask #5
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 19640 KB Output is correct
2 Correct 0 ms 19640 KB Output is correct
3 Correct 0 ms 19640 KB Output is correct
4 Correct 0 ms 19640 KB Output is correct
5 Correct 109 ms 19640 KB Output is correct
6 Correct 215 ms 19640 KB Output is correct
7 Correct 248 ms 19640 KB Output is correct
8 Correct 289 ms 19640 KB Output is correct
9 Correct 1526 ms 40036 KB Output is correct
10 Correct 2197 ms 40036 KB Output is correct
11 Correct 1498 ms 40036 KB Output is correct
12 Correct 1230 ms 40036 KB Output is correct
13 Correct 1191 ms 40036 KB Output is correct
14 Correct 1482 ms 40076 KB Output is correct
15 Correct 2210 ms 40076 KB Output is correct
16 Correct 1502 ms 40076 KB Output is correct
17 Correct 1213 ms 40076 KB Output is correct
18 Correct 1297 ms 40076 KB Output is correct