Submission #772093

#	Time	Username	Problem	Language	Result	Execution time	Memory
772093		davitmarg	Circle selection (APIO18_circle_selection)	C++17	72 / 100	3016 ms	44872 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;
unordered_map<LL, vector<circle>> g;
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) % mod;
}

void changeScale()
{
   g.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++)
            {
                if (g.find(H(MP(kx, ky))) == g.end())
                    continue;
                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:115: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]
  115 |                 for (int j = 0; j < c.size(); j++)
      |                                 ~~^~~~~~~~~~
circle_selection.cpp:84:9: warning: unused variable 'cur' [-Wunused-variable]
   84 |     int cur = 0;
      |         ^~~

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