Submission #772050

#	Time	Username	Problem	Language	Result	Execution time	Memory
772050		bgnbvnbv	Park (BOI16_park)	C++14	100 / 100	789 ms	1860 KiB

park

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e4;
const ll inf=1e18;
const ll mod=1e9+7;
ll w,h;

// y la doc
// x la ngang
ll mnx[maxN],mny[maxN],mxx[maxN],mxy[maxN];
bool check(ll i,ll j,ll id,ll bk)
{
    i++,j++;
    if(i==1&&j==2)
    {
        if(mny[id]<=bk&&mxy[id]>=h-bk) return false;
        if((mny[id]<=bk&&mnx[id]<=bk)||(mny[id]<=bk&&mxx[id]>=w-bk)) return false;
    }
    else if(i==1&&j==3)
    {
        if((mny[id]<=bk&&mxy[id]>=h-bk)||(mnx[id]<=bk&&mxx[id]>=w-bk)) return false;
        if((mny[id]<=bk&&mnx[id]<=bk)||(mxx[id]>=w-bk&&mxy[id]>=h-bk)) return false;
    }
    else if(i==1&&j==4)
    {
        if(mnx[id]<=bk&&mxx[id]>=w-bk) return false;
        if((mny[id]<=bk&&mnx[id]<=bk)||(mnx[id]<=bk&&mxy[id]>=h-bk)) return false;
    }
    else if(i==2&&j==3)
    {
        if(mnx[id]<=bk&&mxx[id]>=w-bk) return false;
        if((mny[id]<=bk&&mxx[id]>=w-bk)||(mxx[id]>=w-bk&&mxy[id]>=h-bk)) return false;
    }
    else if(i==2&&j==4)
    {
        if((mny[id]<=bk&&mxy[id]>=h-bk)||(mnx[id]<=bk&&mxx[id]>=w-bk)) return false;
        if((mny[id]<=bk&&mxx[id]>=w-bk)||(mnx[id]<=bk&&mxy[id]>=h-bk)) return false;
    }
    else if(i==3&&j==4)
    {
        if(mny[id]<=bk&&mxy[id]>=h-bk) return false;
        if((mxx[id]>=w-bk&&mxy[id]>=h-bk)||(mnx[id]<=bk&&mxy[id]>=h-bk)) return false ;
    }
    return true;
}
ll n,m;
ll x[maxN],y[maxN],r[maxN];
ll lim[5][5];
ll lab[maxN];
ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
void unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(u==v) return;
    if(lab[u]>lab[v]) swap(u,v);
    lab[u]+=lab[v];
    lab[v]=u;
    mnx[u]=min(mnx[u],mnx[v]);
    mny[u]=min(mny[u],mny[v]);
    mxx[u]=max(mxx[u],mxx[v]);
    mxy[u]=max(mxy[u],mxy[v]);
}
ll dis(ll i,ll j)
{
    return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}

bool chk(ll q,ll k,ll mid)
{
    for(int i=1;i<=n;i++)
    {
        lab[i]=-1;
        mnx[i]=x[i]-r[i]-mid;
        mxx[i]=x[i]+r[i]+mid;
        mny[i]=y[i]-r[i]-mid;
        mxy[i]=y[i]+r[i]+mid;
        for(int j=1;j<i;j++)
        {
            if(dis(i,j)<(r[i]+r[j]+2*mid)*(r[i]+r[j]+2*mid)) unite(i,j);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(findset(i)==i)
        {
            if(check(q,k,i,mid)==false) return false;
        }
    }
    return true;
}
void solve()
{
    cin >> n >> m;
    cin >> w >> h;
    for(int i=1;i<=n;i++)
    {
        cin >> x[i] >> y[i] >> r[i];
    }
    for(int q=0;q<4;q++)
    {
        for(int k=q+1;k<4;k++)
        {
            ll low=0,high=min(w,h)/4;
            while(low<=high)
            {
                ll mid=low+high>>1;
                if(chk(q,k,mid)) low=mid+1;
                else high=mid-1;
            }
            lim[q][k]=high;
        }
    }
    for(int i=1;i<=m;i++)
    {
        ll id,ra;
        cin >> ra >> id;
        id--;
        for(int j=0;j<id;j++)
        {
            //cout << j<<' '<<lim[j][id]<<'\n';
            if(lim[j][id]>=ra) cout << j+1;
        }
        cout << id+1;
        for(int j=id+1;j<4;j++)
        {
            //cout << j<<' '<<lim[id][j]<<'\n';
            if(lim[id][j]>=ra) cout << j+1;
        }
        cout << '\n';
    }
    //cout << lim[0][2];
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

park.cpp: In function 'void solve()':
park.cpp:117:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |                 ll mid=low+high>>1;
      |                        ~~~^~~~~

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42