oj.uz

Submission #579113

# Submission time Handle Problem Language Result Execution time Memory
579113 2022-06-18T11:42:52 Z noedit Circle selection (APIO18_circle_selection) C++17
72 / 100
 3000 ms 248440 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 301010
#define INF 1000000010
pair<pair<int, int>, pair<int, int>> in[MAXN];
int X[MAXN];
int Y[MAXN];
int R[MAXN];
int ind[MAXN];
int ri[MAXN];
int ans[MAXN];
inline ll sq(ll x)
{
    return x * x;
}
inline bool check(int i, int j)
{
    return sq(X[i] - X[j]) + sq(Y[i] - Y[j]) <= sq(R[i] + R[j]);
}
bool isrange(int x, int y)
{
    if (x < 0 || y < 0)
    {
        return false;
    }
    return true;
}
inline ll trans(int x, int y)
{
    return ((ll)x * (ll)INF) + y;
}
bool cmp(pair<pair<int, int>, pair<int, int>>& p1, pair<pair<int, int>, pair<int, int>>& p2)
{
    if (p1.first.first == p2.first.first)
    {
        return p1.first.second < p2.first.second;
    }
    else
    {
        return p1.first.first > p2.first.first;
    }
}

unordered_map<ll, vector<int>> mp;

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> in[i].second.first >> in[i].second.second >> in[i].first.first, in[i].first.second = i;
    }
    sort(in + 1, in + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        tie(X[i], Y[i], R[i], ind[i]) = make_tuple(in[i].second.first + INF, in[i].second.second + INF, in[i].first.first, in[i].first.second);
    }
    int s, e;
    e = 0;
    for (int k = 30; k >= 0; k--)
    {
        int r = 1 << k;
        s = e + 1;
        if (R[s] < r / 2)
        {
            continue;
        }
        mp.clear();
        e = 0;
        for (int i = s; i <= n; i++)
        {
            if (ans[i])
            {
                continue;
            }
            int x = X[i] >> k;
            int y = Y[i] >> k;
            if (R[i] < r / 2 && !e)
            {
                e = i - 1;
            }
            for (int xx = x - 1; xx <= x + 1; xx++)
            {
                for (int yy = y - 1; yy <= y + 1; yy++)
                {
                    mp[((ll)xx << 31LL) + yy].push_back(i);
                }
            }
        }
        if (e == 0)
        {
            e = n;
        }
        for (int i = s; i <= e; i++)
        {
            if (ans[i])
            {
                continue;
            }
            ans[i] = i;
            int x, y;
            x = X[i] >> k;
            y = Y[i] >> k;
            for (int xx = x - 1; xx <= x + 1; xx++)
            {
                for (int yy = y - 1; yy <= y + 1; yy++)
                {
                    ll t = ((ll)xx << 31LL) + yy;
                    for (auto& c : mp[t])
                    {
                        if (!ans[c] && check(c, i))
                        {
                            ans[c] = i;
                        }
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        ri[ind[i]] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        cout << ind[ans[ri[i]]] << ' ';
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 4 ms 724 KB Output is correct
20 Correct 3 ms 724 KB Output is correct
21 Correct 4 ms 780 KB Output is correct
22 Correct 22 ms 4784 KB Output is correct
23 Correct 23 ms 4796 KB Output is correct
24 Correct 25 ms 4784 KB Output is correct
25 Correct 19 ms 4764 KB Output is correct
26 Correct 20 ms 4764 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 22112 KB Output is correct
2 Correct 201 ms 22120 KB Output is correct
3 Correct 203 ms 22320 KB Output is correct
4 Correct 215 ms 21808 KB Output is correct
5 Correct 318 ms 33652 KB Output is correct
6 Correct 1506 ms 65080 KB Output is correct
7 Correct 375 ms 32224 KB Output is correct
8 Correct 577 ms 39996 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 952 ms 84444 KB Output is correct
3 Correct 2752 ms 247212 KB Output is correct
4 Correct 2755 ms 247312 KB Output is correct
5 Execution timed out 3070 ms 162932 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1528 ms 248268 KB Output is correct
2 Correct 1452 ms 248440 KB Output is correct
3 Correct 502 ms 37312 KB Output is correct
4 Correct 1399 ms 248340 KB Output is correct
5 Correct 1435 ms 248396 KB Output is correct
6 Correct 354 ms 32056 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 4 ms 724 KB Output is correct
20 Correct 3 ms 724 KB Output is correct
21 Correct 4 ms 780 KB Output is correct
22 Correct 22 ms 4784 KB Output is correct
23 Correct 23 ms 4796 KB Output is correct
24 Correct 25 ms 4784 KB Output is correct
25 Correct 19 ms 4764 KB Output is correct
26 Correct 20 ms 4764 KB Output is correct
27 Correct 7 ms 1236 KB Output is correct
28 Correct 7 ms 1236 KB Output is correct
29 Correct 8 ms 1140 KB Output is correct
30 Correct 40 ms 9288 KB Output is correct
31 Correct 75 ms 9336 KB Output is correct
32 Correct 47 ms 9316 KB Output is correct
33 Correct 73 ms 7520 KB Output is correct
34 Correct 71 ms 7540 KB Output is correct
35 Correct 78 ms 7908 KB Output is correct
36 Correct 984 ms 86596 KB Output is correct
37 Correct 939 ms 86576 KB Output is correct
38 Correct 1026 ms 86384 KB Output is correct
39 Correct 691 ms 17660 KB Output is correct
40 Correct 718 ms 17696 KB Output is correct
41 Correct 728 ms 17692 KB Output is correct
42 Correct 172 ms 15176 KB Output is correct
43 Correct 452 ms 81772 KB Output is correct
44 Correct 670 ms 81848 KB Output is correct
45 Correct 458 ms 81704 KB Output is correct
46 Correct 504 ms 81748 KB Output is correct
47 Correct 519 ms 81812 KB Output is correct
48 Correct 500 ms 81748 KB Output is correct
49 Correct 520 ms 81972 KB Output is correct
50 Correct 464 ms 81796 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 4 ms 724 KB Output is correct
20 Correct 3 ms 724 KB Output is correct
21 Correct 4 ms 780 KB Output is correct
22 Correct 22 ms 4784 KB Output is correct
23 Correct 23 ms 4796 KB Output is correct
24 Correct 25 ms 4784 KB Output is correct
25 Correct 19 ms 4764 KB Output is correct
26 Correct 20 ms 4764 KB Output is correct
27 Correct 209 ms 22112 KB Output is correct
28 Correct 201 ms 22120 KB Output is correct
29 Correct 203 ms 22320 KB Output is correct
30 Correct 215 ms 21808 KB Output is correct
31 Correct 318 ms 33652 KB Output is correct
32 Correct 1506 ms 65080 KB Output is correct
33 Correct 375 ms 32224 KB Output is correct
34 Correct 577 ms 39996 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 952 ms 84444 KB Output is correct
37 Correct 2752 ms 247212 KB Output is correct
38 Correct 2755 ms 247312 KB Output is correct
39 Execution timed out 3070 ms 162932 KB Time limit exceeded
40 Halted 0 ms 0 KB -