제출 #32269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32269		dqhungdl	Spiral (BOI16_spiral)	C++14	27 / 100	63 ms	33580 KiB

spiral

#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
int n,T;
int64_t a[2005][2005];

void Sub1()
{
    a[n+1][n+1]=1;
    int ii=1,jj=0,Count=1;
    for(int i=1;i<=n;i++)
    {
        while(jj<=i)
        {
            a[ii+n+1][jj+n+1]=++Count;
            jj++;
        }
        jj--;
        ii--;
        while(ii>=-i)
        {
            a[ii+n+1][jj+n+1]=++Count;
            ii--;
        }
        ii++;
        jj--;
        while(jj>=-i)
        {
            a[ii+n+1][jj+n+1]=++Count;
            jj--;
        }
        jj++;
        ii++;
        while(ii<=i)
        {
            a[ii+n+1][jj+n+1]=++Count;
            ii++;
        }
    }
    for(int i=1;i<=2*n+1;i++)
        for(int j=1;j<=2*n+1;j++)
            a[i][j]=(a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1]+mod)%mod;
    int u1,v1,u2,v2;
    while(T--)
    {
        cin>>u1>>v1>>u2>>v2;
        u1+=n+1;
        v1+=n+1;
        u2+=n+1;
        v2+=n+1;
        cout<<(a[u2][v2]-a[u1-1][v2]-a[u2][v1-1]+a[u1-1][v1-1]+2*mod)%mod<<"\n";
    }
}

void Sub2(int u,int v)
{
    int64_t Class=max(abs(u)-1,abs(v)-1);
    int64_t Count=(2*Class+1)*(2*Class+1)+1;
    int i=Class+1,j=-Class;
    if(u==i&&v>=j)
    {
        cout<<(Count+v-j)%mod<<"\n";
        return;
    }
    Count+=2*Class+2;
    i=Class,j=Class+1;
    if(u<=i&&v==j)
    {
        cout<<(Count+i-u)%mod<<"\n";
        return;
    }
    Count+=2*Class+2;
    i=-Class-1,j=Class;
    if(u==i&&v<=j)
    {
        cout<<(Count+j-v)%mod<<"\n";
        return;
    }
    Count+=2*Class+2;
    i=-Class,j=-Class-1;
    if(u>=i&&v==j)
    {
        cout<<(Count+u-i)%mod<<"\n";
        return;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("SPIRAL.INP","r",stdin);
    cin>>n>>T;
    if(n<=1000)
        Sub1();
    else
    {
        int u1,v1,u2,v2;
        while(T--)
        {
            cin>>u1>>v1>>u2>>v2;
            if(u1==u2&&v1==v2)
                Sub2(u1,v1);
        }
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 31
• Subtask 5: 0 / 25