Submission #772099

#	Time	Username	Problem	Language	Result	Execution time	Memory
772099		davitmarg	Circle selection (APIO18_circle_selection)	C++17	100 / 100	990 ms	226616 KiB

circle_selection

/*
DavitMarg
In pr honky-tonk,
Down in Mexico
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair    
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 500005;

#define circle pair<pair<LL, LL>, pair<LL, int>>
#define X first.first
#define Y first.second
#define R second.first
#define I second.second

int n;
circle p[N];
LL rad;
vector<circle> g[N];
int ans[N];

bool intersect(circle a, circle b)
{
    LL dx = a.X - b.X;
    LL dy = a.Y - b.Y;
    return (dx * dx) + (dy * dy) <= (a.R + b.R) * (a.R + b.R);
}

LL prm = 271;

LL H(pair<LL, LL> xy)
{
    return ((prm * xy.first) + xy.second) % (N - 100);
}

void changeScale()
{
   for (int i = 0; i < N - 100; i++)
       g[i].clear();
   for (int i = 1; i <= n; i++)
       g[H(MP(p[i].X / rad, p[i].Y / rad))].push_back(p[i]);
}


void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].X >> p[i].Y >> p[i].R;
        p[i].X += mod;
        p[i].Y += mod;
        p[i].I = i;
        rad = max(rad, p[i].R);
    }

    


    int cur = 0;

    sort(p + 1, p + 1 + n, [](circle a, circle b) {
        if(a.R != b.R)
            return a.R > b.R;
        return a.I < b.I;
    });

    changeScale();

    for (int i = 1; i <= n; i++)
    {
        if (ans[p[i].I])
            continue;

        if (p[i].R * 2 < rad)
        {
            while (p[i].R * 2 < rad)
                rad /= 2;
            changeScale();
        }

        LL x = p[i].X / rad;
        LL y = p[i].Y / rad;

        for(int kx = x - 2; kx <= x + 2; kx++)
            for (int ky = y - 2; ky <= y + 2; ky++)
            {
                vector<circle>& c = g[H(MP(kx, ky))];
                for (int j = 0; j < c.size(); j++)
                {
                    if (ans[c[j].I])
                        continue;
                    if(intersect(p[i], c[j]))
                        ans[c[j].I] = p[i].I;
                }
            }
    }

    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;

}

int main()
{
    fastIO;
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

/*

11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1


*/

Compilation message (stderr)

circle_selection.cpp: In function 'void solve()':
circle_selection.cpp:114:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                 for (int j = 0; j < c.size(); j++)
      |                                 ~~^~~~~~~~~~
circle_selection.cpp:85:9: warning: unused variable 'cur' [-Wunused-variable]
   85 |     int cur = 0;
      |         ^~~

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