Submission #1250676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250676		trinm01	Park (BOI16_park)	C++20	0 / 100	131 ms	327680 KiB

park

//  #pragma GCC optimize("O3")
//  #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzd,popd")
#include <bits/stdc++.h>
using namespace std;

// #define int long long 
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first    
#define se second
#define pii pair<int, int>

const ll mod = 111539768;
const int MAXN = 5e6 + 5;
const int oo = 1e18 + 7;
const ll base = 320;  

int n, m, w, h;
struct cay{
    int x, y, r;
}a[MAXN];
struct ng{
    int r, e, ps;
    string kq;
}b[MAXN];

vector<pii> mp[MAXN];
vector<double> vec;
double kc(int x, int y, int xx, int yy){
    return (double(sqrt((double(x-xx)*double(x-xx))+(double(y-yy)*double(y-yy)))));
}

bool cmp(ng a, ng b){
    return a.r<b.r;
}
bool cmp2(ng a, ng b){
    return a.ps<b.ps;
}

int par[MAXN];
int find(int u){
    if(u==par[u]){
        return u;
    }
    return par[u]=find(par[u]);
}
void join(int u, int v){
    u=find(u);
    v=find(v);
    if(u==v){
        return;
    }
    par[v]=u;
}

int chk(int u, int v){
    return find(u)==find(v);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);   

    //   freopen("test.txt", "r", stdin);
    //    freopen("o2.out", "w", stdout);
    if(fopen(".inp", "r")){
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }

    cin >> n >> m;
    cin >> h >> w;
    FOR(i, 5, n+4){
        int x, y, r;
        cin >> x >> y >> r;
        a[i]={x, y, r};
    }
    FOR(i, 1, m){
        int r, c;
        cin >> r >> c;
        b[i]={r, c, i, ""};
    }

    FOR(i, 5, n+4){
        auto [x, y, r]=a[i];
        vec.push_back(double(x-r));
        vec.push_back(double(h-(x+r)));
        vec.push_back(double(y-r));
        vec.push_back(double(w-(y+r)));
        FOR(j, 5, n+4){
            if(i!=j){
                auto [x, y, r]=a[i];
                auto [xx, yy, rr]=a[j];
                vec.push_back(kc(x, y, xx, yy)-r-rr);
            }
        }
    }    
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    FOR(i, 5, n+4){
        auto [x, y, r]=a[i];
        mp[lower_bound(vec.begin(), vec.end(), double(x-r))-vec.begin()].push_back({i, 4});
        mp[lower_bound(vec.begin(), vec.end(), double(h-(x+r)))-vec.begin()].push_back({i, 2});
        mp[lower_bound(vec.begin(), vec.end(), double(y-r))-vec.begin()].push_back({i, 3});
        mp[lower_bound(vec.begin(), vec.end(), double(w-(y+r)))-vec.begin()].push_back({i, 1});
        FOR(j, 5, n+4){
            if(i!=j){
                auto [x, y, r]=a[i];
                auto [xx, yy, rr]=a[j];
                mp[lower_bound(vec.begin(), vec.end(), kc(x, y, xx, yy)-r-rr)-vec.begin()].push_back({i, j});
            }
        }
    }

    sort(b+1, b+1+m, cmp);

    
    FOR(i, 1, n+5){
        par[i]=i;
    }
    // for(auto x:vec){
    //     // cout << x << "  ";
    //     for(auto [u, v]:mp[lower_bound(vec[i])]){
    //         // cout << u << ' ' << v << "  ";
    //         // join(u, v);
    //     }
    //     // cout << '\n';
    // }
    int j=0;
    FOR(i, 1, m){
        auto [r, e, ps, kq]=b[i];
        r*=2;
        while(j<=vec.size()-1 && vec[j]<r){
            // cout << vec[j] << "  ";
            for(auto [u, v]:mp[j]){
                // cout << u << ' ' << v << "  ";
                join(u, v);
            }
            j++;
            // cout << '\n';
        }
        string s=to_string(e);
        if(e==1){
            if(!chk(3, 4) && !chk(1, 3) && !chk(2, 3)){
                s+='2';
            }
            if(!chk(3, 4) && !chk(1, 3) && !chk(4, 2) && !chk(1, 2)){
                s+='3';
            }
            if(!chk(3, 4) && !chk(2, 4) && !chk(1, 4)){
                s+='4';
            }
        }
        else if(e==2){
            if(!chk(3, 2) && !chk(1, 3) && !chk(3, 4)){
                s+='1';
            }
            if(!chk(3, 2) && !chk(2, 4) && !chk(1, 2)){
                s+='3';
            }
            if(!chk(3, 2) && !chk(2, 4) && !chk(1, 3) && !chk(1, 4)){
                s+='4';
            }
        }
        else if(e==3){
            if(!chk(1, 2) && !chk(1, 3) && !chk(2, 4) && !chk(3, 4)){
                s+='1';
            }
            if(!chk(1, 2) && !chk(2, 4) && !chk(3, 2)){
                s+='2';
            }
            if(!chk(1, 2) && !chk(1, 3) && !chk(1, 4)){
                s+='4';
            }
        }
        else if(e==4){
            if(!chk(1, 4) && !chk(2, 4) && !chk(3, 4)){
                s+='1';
            }
            if(!chk(1, 4) && !chk(2, 4) && !chk(1, 3) && !chk(3, 2)){
                s+='2';
            }
            if(!chk(1, 4) && !chk(1, 3) && !chk(1, 4)){
                s+='3';
            }
        }
        // cout << s;
        sort(s.begin(), s.end());
        b[i].kq=s;
    }

    sort(b+1, b+1+m, cmp2);
    FOR(i, 1, m){
        cout << b[i].kq << '\n';
    }

    return 0;
}

Compilation message (stderr)

park.cpp:17:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   17 | const int oo = 1e18 + 7;
      |                ~~~~~^~~
park.cpp: In function 'int main()':
park.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
park.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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