oj.uz

Submission #160534

# Submission time Handle Problem Language Result Execution time Memory
160534 2019-10-28T10:49:39 Z Minnakhmetov Circle selection (APIO18_circle_selection) C++14
72 / 100
 3000 ms 53864 KB 
#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
  
using namespace std;

struct C {
    ll x, y, r, i;
};

const int N = 3e5 + 5, INF = 1e9;
map<pair<ll, ll>, vector<int>> mp;
bool used[N];
C cir[N];
int n;
int ans[N];

bool check(const C &a, const C &b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) <= 
        (a.r + b.r) * (a.r + b.r);
}

void build(int r) {
    mp.clear();
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            mp[{cir[i].x / r, cir[i].y / r}].push_back(i);
        }
    }
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n;

    int cur = 0;

    for (int i = 0; i < n; i++) {
        cin >> cir[i].x >> cir[i].y >> cir[i].r;
        cir[i].x += INF;
        cir[i].y += INF;
        cir[i].i = i;
    }

    sort(cir, cir + n, [](const C &a, const C &b) {
        return a.r == b.r ? a.i < b.i : a.r > b.r;
    });

    cur = cir[0].r;

    build(cur);

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            // cout << cir[i].x << " " << cir[i].y << " " << cir[i].r << "\n";

            if (cir[i].r * 2 < cur) {
                cur = cir[i].r;
                build(cur);
            }

            int x = cir[i].x / cur,
                y = cir[i].y / cur;

            for (int j = x - 3; j <= x + 3; j++) {
                for (int k = y - 3; k <= y + 3; k++) {
                    if (mp.count({j, k})) {
                        vector<int> &v = mp[{j, k}];
                        for (int h = 0; h < v.size(); h++) {
                            if (check(cir[i], cir[v[h]])) {
                                ans[cir[v[h]].i] = cir[i].i;
                                used[v[h]] = 1;
                                swap(v.back(), v[h]);
                                v.pop_back();
                                h--;
                            }
                        }
                    }
                    
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << ans[i] + 1 << " ";
    }
 
    return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:72:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (int h = 0; h < v.size(); h++) {
                                         ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 316 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 380 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 5 ms 632 KB Output is correct
20 Correct 5 ms 628 KB Output is correct
21 Correct 5 ms 632 KB Output is correct
22 Correct 21 ms 1144 KB Output is correct
23 Correct 23 ms 1060 KB Output is correct
24 Correct 21 ms 1148 KB Output is correct
25 Correct 19 ms 1144 KB Output is correct
26 Correct 20 ms 1144 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 13600 KB Output is correct
2 Correct 209 ms 13652 KB Output is correct
3 Correct 205 ms 14696 KB Output is correct
4 Correct 202 ms 13864 KB Output is correct
5 Correct 286 ms 14168 KB Output is correct
6 Correct 1049 ms 34292 KB Output is correct
7 Correct 373 ms 20060 KB Output is correct
8 Correct 513 ms 24312 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 735 ms 15492 KB Output is correct
3 Correct 2777 ms 46028 KB Output is correct
4 Correct 2752 ms 46584 KB Output is correct
5 Correct 2593 ms 40032 KB Output is correct
6 Correct 870 ms 24104 KB Output is correct
7 Correct 371 ms 13176 KB Output is correct
8 Correct 54 ms 3060 KB Output is correct
9 Execution timed out 3037 ms 51384 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2534 ms 46324 KB Output is correct
2 Correct 1642 ms 53280 KB Output is correct
3 Correct 827 ms 31348 KB Output is correct
4 Correct 1740 ms 53664 KB Output is correct
5 Correct 1676 ms 53864 KB Output is correct
6 Correct 350 ms 25128 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 316 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 380 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 5 ms 632 KB Output is correct
20 Correct 5 ms 628 KB Output is correct
21 Correct 5 ms 632 KB Output is correct
22 Correct 21 ms 1144 KB Output is correct
23 Correct 23 ms 1060 KB Output is correct
24 Correct 21 ms 1148 KB Output is correct
25 Correct 19 ms 1144 KB Output is correct
26 Correct 20 ms 1144 KB Output is correct
27 Correct 9 ms 888 KB Output is correct
28 Correct 9 ms 888 KB Output is correct
29 Correct 9 ms 888 KB Output is correct
30 Correct 46 ms 1912 KB Output is correct
31 Correct 43 ms 1912 KB Output is correct
32 Correct 44 ms 1912 KB Output is correct
33 Correct 74 ms 5124 KB Output is correct
34 Correct 73 ms 5080 KB Output is correct
35 Correct 78 ms 4804 KB Output is correct
36 Correct 653 ms 15508 KB Output is correct
37 Correct 651 ms 15712 KB Output is correct
38 Correct 679 ms 15608 KB Output is correct
39 Correct 607 ms 13972 KB Output is correct
40 Correct 618 ms 15048 KB Output is correct
41 Correct 589 ms 15056 KB Output is correct
42 Correct 510 ms 17144 KB Output is correct
43 Correct 473 ms 17912 KB Output is correct
44 Correct 450 ms 17912 KB Output is correct
45 Correct 454 ms 18040 KB Output is correct
46 Correct 481 ms 17912 KB Output is correct
47 Correct 467 ms 17912 KB Output is correct
48 Correct 467 ms 17876 KB Output is correct
49 Correct 454 ms 17884 KB Output is correct
50 Correct 477 ms 18040 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 316 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 380 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 5 ms 632 KB Output is correct
20 Correct 5 ms 628 KB Output is correct
21 Correct 5 ms 632 KB Output is correct
22 Correct 21 ms 1144 KB Output is correct
23 Correct 23 ms 1060 KB Output is correct
24 Correct 21 ms 1148 KB Output is correct
25 Correct 19 ms 1144 KB Output is correct
26 Correct 20 ms 1144 KB Output is correct
27 Correct 204 ms 13600 KB Output is correct
28 Correct 209 ms 13652 KB Output is correct
29 Correct 205 ms 14696 KB Output is correct
30 Correct 202 ms 13864 KB Output is correct
31 Correct 286 ms 14168 KB Output is correct
32 Correct 1049 ms 34292 KB Output is correct
33 Correct 373 ms 20060 KB Output is correct
34 Correct 513 ms 24312 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 735 ms 15492 KB Output is correct
37 Correct 2777 ms 46028 KB Output is correct
38 Correct 2752 ms 46584 KB Output is correct
39 Correct 2593 ms 40032 KB Output is correct
40 Correct 870 ms 24104 KB Output is correct
41 Correct 371 ms 13176 KB Output is correct
42 Correct 54 ms 3060 KB Output is correct
43 Execution timed out 3037 ms 51384 KB Time limit exceeded
44 Halted 0 ms 0 KB -