oj.uz

Submission #579090

# Submission time Handle Problem Language Result Execution time Memory
579090 2022-06-18T11:21:47 Z noedit Circle selection (APIO18_circle_selection) C++17
37 / 100
 3000 ms 133908 KB 
#include <bits/stdc++.h>
#define sz(x) (x.size())
using namespace std;
typedef long long ll;
//#define int long long
#define INF 1000000010
#define MAXN 300000

pair<pair<int, int>, pair<int, int> > in[MAXN];

int X[MAXN], Y[MAXN], R[MAXN];
int ind[MAXN];
int ans[MAXN];
int ri[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]);
}

inline bool isrange(int x, int y)
{
    if (x < 0 || y < 0)
        return false;
    return true;
}

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;

void solve()
{

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int i;
    for (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 (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 k;
    int s, e;
    e = 0;
    for (k = 30; k >= 0; k--)
    {
        int r = (1 << k);
        s = e + 1;
        if (R[s] < r / 2)
        {
            continue;
        }
        mp.clear();
        e = 0;
        for (i = s; i <= n; i++)
        {
            if (ans[i])
            {
                continue;
            }
            int x, y;
            x = X[i] >> k;
            y = Y[i] >> k;
            if (R[i] < r / 2 && !e)
            {
                e = i - 1;
            }
            int xx, yy;
            for (xx = x - 1; xx <= x + 1; xx++)
            {
                for (yy = y - 1; yy <= y + 1; yy++)
                {
                    mp[(ll)xx << 31LL + yy].push_back(i);
                }
            }
        }
        if (e == 0)
        {
            e = n;
        }
        for (i = s; i <= e; i++)
        {
            if (ans[i])
            {
                continue;
            }
            ans[i] = i;
            int x = X[i] >> k;
            int y = Y[i] >> k;
            int xx, yy;
            for (xx = x - 1; xx <= x + 1; xx++)
            {
                for (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 (i = 1; i <= n; i++)
    {
        ri[ind[i]] = i;
    }
    for (i = 1; i <= n; i++)
    {
        cout << ind[ans[ri[i]]] << ' ';
    }
    return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:100:39: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  100 |                     mp[(ll)xx << 31LL + yy].push_back(i);
      |                                  ~~~~~^~~~
circle_selection.cpp:122:44: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  122 |                     ll t = ((ll)xx << 31LL + yy);
      |                                       ~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 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 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 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 852 KB Output is correct
21 Correct 4 ms 724 KB Output is correct
22 Correct 19 ms 3632 KB Output is correct
23 Correct 20 ms 1748 KB Output is correct
24 Correct 23 ms 3704 KB Output is correct
25 Correct 21 ms 3888 KB Output is correct
26 Correct 24 ms 3632 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 24528 KB Output is correct
2 Correct 219 ms 23620 KB Output is correct
3 Correct 207 ms 22764 KB Output is correct
4 Correct 193 ms 23720 KB Output is correct
5 Correct 366 ms 33740 KB Output is correct
6 Execution timed out 3060 ms 46928 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1633 ms 23132 KB Output is correct
3 Execution timed out 3087 ms 56836 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 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 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 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 852 KB Output is correct
21 Correct 4 ms 724 KB Output is correct
22 Correct 19 ms 3632 KB Output is correct
23 Correct 20 ms 1748 KB Output is correct
24 Correct 23 ms 3704 KB Output is correct
25 Correct 21 ms 3888 KB Output is correct
26 Correct 24 ms 3632 KB Output is correct
27 Correct 7 ms 1236 KB Output is correct
28 Correct 8 ms 1236 KB Output is correct
29 Correct 7 ms 1236 KB Output is correct
30 Correct 43 ms 5084 KB Output is correct
31 Correct 56 ms 6712 KB Output is correct
32 Correct 54 ms 6852 KB Output is correct
33 Correct 68 ms 8172 KB Output is correct
34 Correct 66 ms 7996 KB Output is correct
35 Correct 76 ms 7856 KB Output is correct
36 Correct 1827 ms 53864 KB Output is correct
37 Correct 1675 ms 53496 KB Output is correct
38 Correct 1809 ms 49220 KB Output is correct
39 Correct 1251 ms 11956 KB Output is correct
40 Correct 1294 ms 11976 KB Output is correct
41 Correct 1198 ms 11888 KB Output is correct
42 Correct 538 ms 10768 KB Output is correct
43 Correct 1685 ms 61856 KB Output is correct
44 Correct 1693 ms 61656 KB Output is correct
45 Correct 1673 ms 61624 KB Output is correct
46 Correct 1796 ms 62104 KB Output is correct
47 Correct 1614 ms 61708 KB Output is correct
48 Correct 1719 ms 61880 KB Output is correct
49 Correct 1750 ms 61980 KB Output is correct
50 Correct 1621 ms 61800 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 1 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 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 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 852 KB Output is correct
21 Correct 4 ms 724 KB Output is correct
22 Correct 19 ms 3632 KB Output is correct
23 Correct 20 ms 1748 KB Output is correct
24 Correct 23 ms 3704 KB Output is correct
25 Correct 21 ms 3888 KB Output is correct
26 Correct 24 ms 3632 KB Output is correct
27 Correct 193 ms 24528 KB Output is correct
28 Correct 219 ms 23620 KB Output is correct
29 Correct 207 ms 22764 KB Output is correct
30 Correct 193 ms 23720 KB Output is correct
31 Correct 366 ms 33740 KB Output is correct
32 Execution timed out 3060 ms 46928 KB Time limit exceeded
33 Halted 0 ms 0 KB -