Submission #201239

#	Time	Username	Problem	Language	Result	Execution time	Memory
201239		gs18115	여왕벌 (KOI15_queen)	C++14	101 / 100	3658 ms	166956 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
int op[710][710][3][3][3];
int dp[710][710];
inline void calc(int sz,int mn,int nsz,vector<vector<int> >&in,vector<vector<int> >&in1)
{
    in1.clear();
    in1.resize(nsz,vector<int>(nsz,0));
    for(int i=0;i<sz;i++)
    {
        for(int j=0;i+j<sz;j++)
        {
            int ni=min(max(i,mn)-mn,nsz-1);
            int nj=min(max(i+j,mn)-mn,nsz-1)-ni;
            in1[ni][nj]+=in[i][j];
        }
    }
    return;
}
inline void app(int sz,int mn,int nsz,vector<vector<int> >&in,
vector<vector<pi> >&out,vector<vector<int> >&in1,vector<vector<pi> >&out1)
{
    vector<vector<int> >t=in;
    in.clear();
    in.resize(sz,vector<int>(sz,0));
    out.resize(sz,vector<pi>(sz,pi(0,0)));
    for(int i=0;i<sz;i++)
    {
        for(int j=0;i+j<sz;j++)
        {
            int ni=min(max(i,mn)-mn,nsz-1);
            int nj=min(max(i+j,mn)-mn,nsz-1)-ni;
            if(ni==0)
            {
                if(nj==0||nj==nsz-1)
                    out[i][j]=pi(i,j);
                else
                    out[i][j]=pi(i,mn-i+out1[ni][nj].se);
            }
            else if(ni+nj==nsz-1)
            {
                if(ni==0||nj==0)
                    out[i][j]=pi(i,j);
                else
                    out[i][j]=pi(mn+out1[ni][nj].fi,out1[ni][nj].se+i+j-mn-nsz+1);
            }
            else
                out[i][j]=pi(mn+out1[ni][nj].fi,out1[ni][nj].se);
            in[out[i][j].fi][out[i][j].se]+=t[i][j];
        }
    }
    return;
}
vector<vector<pi> >dnc(int s,int e,int l,int r,vector<vector<int> >&in)
{
    int sz=r-l+e-s;
    vector<vector<pi> >out(sz,vector<pi>(sz,pi(0,0))),o1,o2,o3,o4;
    vector<vector<int> >in1;
    for(int i=0;i<sz;i++)
        for(int j=0;i+j<sz;j++)
            out[i][j]=pi(i,j);
    if(e<s+2||r<l+2)
        return out;
    if(e==s+2&&r==l+2)
    {
        for(int i=0;i<4;i++)
        {
            for(int j=0;i+j<4;j++)
            {
                int l2=i>0?0:(i+j>0?1:2);
                int d=i>1?0:(i+j>1?1:2);
                int u=i>2?0:(i+j>2?1:2);
                int nxt=op[s+1][l+1][l2][d][u];
                dp[s+1][l+1]+=nxt*in[i][j];
                out[i][j]=pi((l2==0)+(nxt==0)+(u==0),(l2==1)+(nxt==1)+(u==1));
            }
        }
        return out;
    }
    int mx=s+e>>1;
    int my=l+r>>1;
    int nsz,mn;

    nsz=mx-s+my-l+2;
    mn=e-mx-1;
    calc(sz,mn,nsz,in,in1);
    auto out1=dnc(s,mx+1,l,my+1,in1);
    app(sz,mn,nsz,in,o1,in1,out1);

    nsz=mx-s+r-my+1;
    mn=e-mx-1+my-l;
    calc(sz,mn,nsz,in,in1);
    out1=dnc(s,mx+1,my,r,in1);
    app(sz,mn,nsz,in,o2,in1,out1);

    nsz=e-mx+my-l+1;
    mn=0;
    calc(sz,mn,nsz,in,in1);
    out1=dnc(mx,e,l,my+1,in1);
    app(sz,mn,nsz,in,o3,in1,out1);

    nsz=e-mx+r-my;
    mn=my-l;
    calc(sz,mn,nsz,in,in1);
    out1=dnc(mx,e,my,r,in1);
    app(sz,mn,nsz,in,o4,in1,out1);

    for(int i=0;i<sz;i++)
    {
        for(int j=0;i+j<sz;j++)
        {
            out[i][j]=o1[out[i][j].fi][out[i][j].se];
            out[i][j]=o2[out[i][j].fi][out[i][j].se];
            out[i][j]=o3[out[i][j].fi][out[i][j].se];
            out[i][j]=o4[out[i][j].fi][out[i][j].se];
        }
    }

    return out;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            dp[i][j]=1;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<n;j++)
        {
            string s;
            cin>>s;
            for(int l=0;l<3;l++)
                for(int d=0;d<3;d++)
                    for(int u=0;u<3;u++)
                        op[i][j][l][d][u]=s[l*9+d*3+u]=='L'?l:(s[l*9+d*3+u]=='D'?d:u);
        }
    }
    int sz=n*2;
    vector<vector<int> >in(sz,vector<int>(sz,0));
    vector<int>ps(sz,0);
    for(int i=0;i<q;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        in[x][y]++;
        ps[x]++;
        ps[x+y]++;
    }
    ps[0]++;
    for(int i=1;i<sz;i++)
        ps[i]+=ps[i-1];
    for(int i=0;i<n;i++)
        dp[n-i-1][0]=ps[i];
    for(int i=n;i<sz;i++)
        dp[0][i-n+1]=ps[i];
    dnc(0,n,0,n,in);
    for(int i=0;i<n;i++,cout<<endl)
        for(int j=0;j<n;j++)
            cout<<dp[i][j]<<' ';
    return 0;
}

Compilation message (stderr)

queen.cpp: In function 'std::vector<std::vector<std::pair<int, int> > > dnc(int, int, int, int, std::vector<std::vector<int> >&)':
queen.cpp:94:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mx=s+e>>1;
            ~^~
queen.cpp:95:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int my=l+r>>1;
            ~^~

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