Submission #51892

#	Time	Username	Problem	Language	Result	Execution time	Memory
51892		Alexa2001	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1816 ms	524636 KiB

circle_selection

#include <bits/stdc++.h>

/// 13:07

using namespace std;

typedef pair<int,int> Pair;
typedef long long ll;
const int Nmax = 3e5 + 5;

int n, i, id, R, lg;
int x[Nmax], y[Nmax], r[Nmax], ans[Nmax];
Pair ord[Nmax];
vector< vector<Pair> > v;
vector<int> start;

void rescale()
{
    int i;
    vector< vector<Pair> > nv;
    vector<Pair> q[2];

    for(auto w : v)
    {
        for(i=0; i<2; ++i) q[i].clear();

        for(auto val : w)
            if(!ans[val.second])
                q[(x[val.second] >> lg) & 1].push_back(val);

        for(i=0; i<2; ++i)
            if(q[i].size())
                nv.push_back(q[i]);
    }

    v = nv;
    start.resize(v.size());
    for(i=0; i<v.size(); ++i)
        start[i] = x[v[i][0].second] >> lg;
}

inline ll sq(int x) { return (ll)x*x; }

inline bool intersect(int i, int j)
{
    return sq(x[i] - x[j]) + sq(y[i] - y[j]) <= sq(r[i] + r[j]);
}

int bs(int val)
{
    int pos = 0, bit = 0;
    for(; (1<<bit) < start.size(); ++bit);

    for(--bit; bit>=0; --bit)
        if(pos + (1<<bit) < start.size() && start[pos + (1<<bit)] < val)
            pos += (1<<bit);

    if(!pos) return start[0] < val;
    return pos + 1;
}

void update_ans(int id)
{
    int pos, now, ly, ry, X;
    vector<Pair> :: iterator it;

    /*
    cout << "Writing step\n";
    cerr << v.size() << '\n';
    for(auto w : v)
    {
       cerr << "Another w:\n";
        for(auto val : w) cerr << val.first << ' ' << val.second << '\n';
    }
    */

    X = x[id] >> lg;

    ly = max(0LL, (ll)y[id] - 2 * r[id]);
    ry = min((ll)2e9, (ll)y[id] + 2 * r[id]);

    for(pos = max(0, bs(X) - 2); pos < start.size() && start[pos] <= X + 2; ++pos)
    {
        for(it = upper_bound(v[pos].begin(), v[pos].end(), make_pair(ly, 0) ); it != v[pos].end() && it->first <= ry; ++it)
        {
            now = it->second;
            if(!ans[now] && intersect(id, now))
                    ans[now] = id;
        }
    }
}

int main()
{
 //   freopen("input", "r", stdin);
  //  freopen("output", "w", stdout);

    cin.sync_with_stdio(false);

    int mnX = INT_MAX, mnY = INT_MAX;

    cin >> n;
    v.push_back({});
    for(i=1; i<=n; ++i)
    {
        cin >> x[i] >> y[i] >> r[i];
        ord[i] = {r[i], i};

        mnX = min(mnX, x[i]);
        mnY = min(mnY, y[i]);
    }

    for(i=1; i<=n; ++i)
    {
        x[i] -= mnX, y[i] -= mnY;
        v[0].push_back( {y[i], i} );
    }

    lg = 31;

    sort(v[0].begin(), v[0].end());
    sort(ord+1, ord+n+1,
         [&] (const Pair &a, const Pair &b) { if(a.first == b.first) return a.second < b.second; return a.first > b.first;} );

    for(i=1; i<=n; ++i)
    {
        id = ord[i].second;
        if(ans[id]) continue;

        while(lg && (1<<(lg-1)) >= r[id])
        {
            --lg;
            rescale();
        }

        update_ans(id);
    }

    for(i=1; i<=n; ++i) cout << ans[i] << ' ';
    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'void rescale()':
circle_selection.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v.size(); ++i)
              ~^~~~~~~~~
circle_selection.cpp: In function 'int bs(int)':
circle_selection.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(; (1<<bit) < start.size(); ++bit);
           ~~~~~~~~~^~~~~~~~~~~~~~
circle_selection.cpp:55:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos + (1<<bit) < start.size() && start[pos + (1<<bit)] < val)
            ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
circle_selection.cpp: In function 'void update_ans(int)':
circle_selection.cpp:82:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(pos = max(0, bs(X) - 2); pos < start.size() && start[pos] <= X + 2; ++pos)
                                  ~~~~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13