oj.uz

Submission #201239

# Submission time Handle Problem Language Result Execution time Memory
201239 2020-02-10T01:33:49 Z gs18115 여왕벌 (KOI15_queen) C++14
101 / 100
 3658 ms 166956 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> >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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 508 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 64 ms 4476 KB Output is correct
4 Correct 66 ms 4424 KB Output is correct
5 Correct 579 ms 32576 KB Output is correct
6 Correct 550 ms 32576 KB Output is correct
7 Correct 562 ms 32508 KB Output is correct
8 Correct 1441 ms 87284 KB Output is correct
9 Correct 1384 ms 87172 KB Output is correct
10 Correct 3271 ms 166868 KB Output is correct
11 Correct 3259 ms 166340 KB Output is correct
12 Correct 3377 ms 166440 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Output is correct
2 Correct 572 ms 32716 KB Output is correct
3 Correct 1057 ms 56592 KB Output is correct
4 Correct 3345 ms 166504 KB Output is correct
5 Correct 3203 ms 166676 KB Output is correct
6 Correct 3299 ms 166684 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 66 ms 4548 KB Output is correct
3 Correct 1397 ms 87160 KB Output is correct
4 Correct 3262 ms 166708 KB Output is correct
5 Correct 3294 ms 166708 KB Output is correct
6 Correct 3289 ms 166444 KB Output is correct
7 Correct 3292 ms 166956 KB Output is correct
8 Correct 3239 ms 166892 KB Output is correct
9 Correct 3250 ms 166432 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1710 ms 80592 KB Output is correct
2 Correct 1635 ms 81368 KB Output is correct
3 Correct 3552 ms 154560 KB Output is correct
4 Correct 3586 ms 154476 KB Output is correct
5 Correct 3658 ms 154332 KB Output is correct
6 Correct 3598 ms 154860 KB Output is correct
7 Correct 3602 ms 154692 KB Output is correct
8 Correct 3566 ms 154624 KB Output is correct
9 Correct 3526 ms 154548 KB Output is correct
10 Correct 3534 ms 154408 KB Output is correct

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 218 ms 760 KB Output is correct
6 Correct 209 ms 632 KB Output is correct
7 Correct 216 ms 760 KB Output is correct
8 Correct 216 ms 632 KB Output is correct
9 Correct 3544 ms 153144 KB Output is correct
10 Correct 3548 ms 153744 KB Output is correct
11 Correct 3491 ms 153700 KB Output is correct
12 Correct 3575 ms 153748 KB Output is correct
13 Correct 3585 ms 153580 KB Output is correct
14 Correct 3590 ms 153956 KB Output is correct
15 Correct 3526 ms 154280 KB Output is correct
16 Correct 3598 ms 154716 KB Output is correct
17 Correct 3589 ms 154472 KB Output is correct
18 Correct 3614 ms 154568 KB Output is correct