oj.uz

Submission #864641

# Submission time Handle Problem Language Result Execution time Memory
864641 2023-10-23T11:08:27 Z boris_mihov Circle selection (APIO18_circle_selection) C++17
7 / 100
 3000 ms 8532 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6500 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 6612 KB Output is correct
17 Correct 2 ms 6492 KB Output is correct
18 Correct 3 ms 6492 KB Output is correct
19 Correct 36 ms 6492 KB Output is correct
20 Correct 36 ms 6492 KB Output is correct
21 Correct 35 ms 6488 KB Output is correct
22 Correct 101 ms 6628 KB Output is correct
23 Correct 101 ms 6628 KB Output is correct
24 Correct 102 ms 6628 KB Output is correct
25 Correct 101 ms 6624 KB Output is correct
26 Correct 101 ms 6492 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3013 ms 8532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Execution timed out 3065 ms 7100 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3045 ms 8500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6500 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 6612 KB Output is correct
17 Correct 2 ms 6492 KB Output is correct
18 Correct 3 ms 6492 KB Output is correct
19 Correct 36 ms 6492 KB Output is correct
20 Correct 36 ms 6492 KB Output is correct
21 Correct 35 ms 6488 KB Output is correct
22 Correct 101 ms 6628 KB Output is correct
23 Correct 101 ms 6628 KB Output is correct
24 Correct 102 ms 6628 KB Output is correct
25 Correct 101 ms 6624 KB Output is correct
26 Correct 101 ms 6492 KB Output is correct
27 Correct 138 ms 6488 KB Output is correct
28 Correct 142 ms 6488 KB Output is correct
29 Correct 143 ms 6644 KB Output is correct
30 Correct 525 ms 6492 KB Output is correct
31 Correct 560 ms 6644 KB Output is correct
32 Correct 529 ms 6648 KB Output is correct
33 Execution timed out 3030 ms 7000 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6500 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 6612 KB Output is correct
17 Correct 2 ms 6492 KB Output is correct
18 Correct 3 ms 6492 KB Output is correct
19 Correct 36 ms 6492 KB Output is correct
20 Correct 36 ms 6492 KB Output is correct
21 Correct 35 ms 6488 KB Output is correct
22 Correct 101 ms 6628 KB Output is correct
23 Correct 101 ms 6628 KB Output is correct
24 Correct 102 ms 6628 KB Output is correct
25 Correct 101 ms 6624 KB Output is correct
26 Correct 101 ms 6492 KB Output is correct
27 Execution timed out 3013 ms 8532 KB Time limit exceeded
28 Halted 0 ms 0 KB -