oj.uz

Submission #201234

# Submission time Handle Problem Language Result Execution time Memory
201234 2020-02-10T01:17:22 Z gs18115 여왕벌 (KOI15_queen) C++14
0 / 100
 5000 ms 101900 KB 
#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> >t1;
    vector<vector<pi> >t2;
    t1=in;
    t2=out;
    in.clear();
    in.resize(sz,vector<int>(sz,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)
                    in[i][j]+=t1[i][j],out[i][j]=t2[i][j];
                else
                    in[i][mn-i+out1[ni][nj].se]+=t1[i][j],
                    out[i][j]=t2[i][mn-i+out1[ni][nj].se];
            }
            else if(ni+nj==nsz-1)
            {
                if(ni==0||nj==0)
                    in[i][j]+=t1[i][j],out[i][j]=t2[i][j];
                else
                    in[mn+out1[ni][nj].fi][out1[ni][nj].se+i+j-mn-nsz+1]+=t1[i][j],
                    out[i][j]=t2[mn+out1[ni][nj].fi][out1[ni][nj].se+i+j-mn-nsz+1];
            }
            else
                in[mn+out1[ni][nj].fi][out1[ni][nj].se]+=t1[i][j],
                out[i][j]=t2[mn+out1[ni][nj].fi][out1[ni][nj].se];
        }
    }
    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)));
    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];
                cout<<s+1<<' '<<l+1<<' '<<i<<' '<<j<<' '<<nxt<<' '<<in[i][j]<<endl;
                dp[s+1][l+1]+=nxt*in[i][j];
                out[i][j]=pi((l==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,out,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,out,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,out,in1,out1);

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

    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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5014 ms 101900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -