Submission #1018137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018137		m5588ohammed	Park (BOI16_park)	C++14	0 / 100	1771 ms	1848 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
int UP,DOWN,RIGHT,LEFT,mx[5][5];
int n,m,t,v;
int parent[2010];
vector <array<__int128,3>> rad;
void make_set(int i){
    parent[i]=i;
    return;
}
int find(int a){
    if(parent[a]==a) return a;
    else return parent[a]=find(parent[a]);
}
void merge(int a,int b){
    a=find(a),b=find(b);
    parent[b]=a;
    return;
}
bool UP_DOWN(){ return find(UP)==find(DOWN);}
bool UP_RIGHT(){ return find(UP)==find(RIGHT);}
bool UP_LEFT(){ return find(UP)==find(LEFT);}
bool DOWN_LEFT(){ return find(DOWN)==find(LEFT);}
bool DOWN_RIGHT(){ return find(DOWN)==find(RIGHT);}
bool LEFT_RIGHT(){ return find(LEFT)==find(RIGHT);}

void make(int k){
    for(int i=0;i<=LEFT;i++) make_set(i);
    for(int i=0;i<t;i++){
        auto [x1,y1,r1]=rad[i];
        for(int j=i+1;j<t;j++){
            auto [x2,y2,r2]=rad[j];
            if((__int128)((__int128)(x2-x1)*(__int128)(x2-x1)+((__int128)y2-y1)*(__int128)(y2-y1))<=(__int128)((__int128)(r1+r2+k)*(__int128)(r1+r2+k))) merge(i,j);   
        }
        if((__int128)x1-r1-k<=0) merge(LEFT,i);
        if((__int128)x1+r1+k>=n) merge(RIGHT,i);
        if((__int128)y1-r1-k<=0) merge(UP,i);
        if((__int128)y1+r1+k>=m) merge(DOWN,i);
    }
}
int solve(int st,int en){
    int l=0,r=1e9,ans=0;
    while(l<=r){
        int k=(l+r)/2;
        make(k);
        if(st==1&&en==4){
            if(LEFT_RIGHT()==1||UP_LEFT()==1||DOWN_LEFT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
        if(st==2&&en==4){
            if(LEFT_RIGHT()==1||UP_DOWN()==1||UP_LEFT()==1||DOWN_RIGHT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
        if(st==3&&en==4){
            if(UP_DOWN()==1||UP_LEFT()==1||UP_RIGHT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
        if(st==1&&en==2){
            if(DOWN_LEFT()==1||UP_DOWN()==1||DOWN_RIGHT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
        if(st==1&&en==3){
            if(LEFT_RIGHT()==1||UP_DOWN()==1||DOWN_LEFT()==1||UP_RIGHT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
        if(st==2&&en==3){
            if(LEFT_RIGHT()==1||DOWN_RIGHT()==1||UP_RIGHT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
    }
    return ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>t>>v>>n>>m;
    for(int i=0;i<t;i++){
        int x,y,r;
        cin>>x>>y>>r;
        rad.push_back({(__int128)x,(__int128)y,(__int128)r});
    }
    UP=t+1,DOWN=t+2,RIGHT=t+3,LEFT=t+4;
    for(int d1=1;d1<=4;d1++) for(int d2=d1+1;d2<=4;d2++) mx[d1][d2]=solve(d1,d2);
    while(v--){
        int st,r;
        cin>>r>>st;
        vector <int> ans;
        ans.push_back(st);
        if(mx[min(st,1ll)][max(st,1ll)]>=r*2) ans.push_back(1);
        if(mx[min(st,2ll)][max(st,2ll)]>=r*2) ans.push_back(2);
        if(mx[min(st,3ll)][max(st,3ll)]>=r*2) ans.push_back(3);
        if(mx[min(st,4ll)][max(st,4ll)]>=r*2) ans.push_back(4);
        sort(ans.begin(),ans.end());
        for(int i:ans) cout<<i;
        cout<<endl;
    }

    return 0;
}

Compilation message (stderr)

park.cpp: In function 'void make(long long int)':
park.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |         auto [x1,y1,r1]=rad[i];
      |              ^
park.cpp:34:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |             auto [x2,y2,r2]=rad[j];
      |                  ^

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