Submission #864641

#TimeUsernameProblemLanguageResultExecution timeMemory
864641boris_mihov원 고르기 (APIO18_circle_selection)C++17
7 / 100
3065 ms8532 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...