Submission #864641

#	Time	Username	Problem	Language	Result	Execution time	Memory
864641		boris_mihov	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3065 ms	8532 KiB

circle_selection

#include <algorithm>
#include <iostream>
#include <cassert>
#include <chrono>
#include <vector>
#include <random>
#include <stack>
#include <queue>
#include <set>
#include <map>

#ifdef DEVAL
    #define cerr if (false) cerr
#endif

typedef long long llong;
const int MAXN = 300000 + 10;
const int INF  = 1e9;

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
  
typedef __gnu_pbds::tree <int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> oSet;

std::mt19937 rngNow(std::chrono::high_resolution_clock::now().time_since_epoch().count());
std::mt19937 rng(69420);

int n;
llong x[MAXN];
llong y[MAXN];
llong r[MAXN];
int by[MAXN];

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        int max = 0;
        for (int j = 1 ; j <= n ; ++j)
        {
            if (r[j] > r[max] && by[j] == 0)
            {
                max = j;
            }
        }

        for (int j = 1 ; j <= n ; ++j)
        {
            if (by[j] == 0 && (x[max] - x[j]) * (x[max] - x[j]) + (y[max] - y[j]) * (y[max] - y[j]) <= (r[max] + r[j]) * (r[max] + r[j]))
            {
                by[j] = max;
            }
        }
    }
}

void print()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cout << by[i] << ' ';
    }

    std::cout << '\n';
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> x[i] >> y[i] >> r[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

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