답안 #87169 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87169	2018-11-29T19:57:51 Z	fedoseevtimofey	원 고르기 (APIO18_circle_selection)	C++17	100 / 100	1421 ms	84780 KB

circle_selection

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, int> table;

using namespace std;
 
typedef long long ll;
typedef long double ld;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(pair <int, int> x) const {
        static const uint64_t FIXED_RANDOM1 = chrono::steady_clock::now().time_since_epoch().count();
        static const uint64_t FIXED_RANDOM2 = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM1) ^ splitmix64(x.second + FIXED_RANDOM2);
    }
};
 
int n;
vector <int> x, y, r;
vector <int> _kill;
 
void init() {
    cin >> n;
    x.resize(n);
    y.resize(n);
    r.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> r[i];
    }
}
 
bool inter(int i, int j) {
    return (ll)(x[i] - x[j]) * (x[i] - x[j]) + (ll)(y[i] - y[j]) * (y[i] - y[j]) <= (ll)(r[i] + r[j]) * (r[i] + r[j]);
}
 
gp_hash_table <pair <int, int>, vector <int>, custom_hash> who;
 
 
void rebuild(int B) {
    who.clear();
    for (int i = 0; i < n; ++i) {
        if (_kill[i] != -1) continue;
        int xx = x[i] / B;
        int yy = y[i] / B;
        who[make_pair(xx, yy)].push_back(i);
    }
}
 
void solve() {
    _kill.resize(n, -1);
    vector <int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&] (int i, int j) {
        if (r[i] != r[j]) return r[i] > r[j];
        return i < j;
    });
    int uk = 0;
    int B = 2e9 + 7;
    while (true) {
        while (uk < n && _kill[idx[uk]] != -1) ++uk;
        if (uk == n) break;
        int cur = idx[uk];
        if ((r[cur] << 1) <= B) {
            B = r[cur];
            rebuild(B);
        }
        _kill[cur] = cur;
        int xx = x[cur] / B;
        int yy = y[cur] / B;
        for (int cx = xx - 2; cx <= xx + 2; ++cx) {
            for (int cy = yy - 2; cy <= yy + 2; ++cy) {
                if (who.find(make_pair(cx, cy)) != who.end()) {
                    vector <int> nw;
                    for (auto j : who[make_pair(cx, cy)]) {
                        if (inter(cur, j)) {
                            _kill[j] = cur;
                        }
                        else nw.push_back(j);
                    }
                    who[make_pair(cx, cy)] = nw;
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << _kill[i] + 1 << ' ';
    }
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    init();
    solve();
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	2 ms	372 KB	Output is correct
3	Correct	2 ms	448 KB	Output is correct
4	Correct	3 ms	652 KB	Output is correct
5	Correct	2 ms	652 KB	Output is correct
6	Correct	2 ms	652 KB	Output is correct
7	Correct	2 ms	652 KB	Output is correct
8	Correct	2 ms	652 KB	Output is correct
9	Correct	3 ms	652 KB	Output is correct
10	Correct	2 ms	652 KB	Output is correct
11	Correct	2 ms	652 KB	Output is correct
12	Correct	2 ms	652 KB	Output is correct
13	Correct	2 ms	652 KB	Output is correct
14	Correct	2 ms	652 KB	Output is correct
15	Correct	2 ms	652 KB	Output is correct
16	Correct	3 ms	652 KB	Output is correct
17	Correct	4 ms	652 KB	Output is correct
18	Correct	3 ms	652 KB	Output is correct
19	Correct	6 ms	732 KB	Output is correct
20	Correct	6 ms	732 KB	Output is correct
21	Correct	5 ms	748 KB	Output is correct
22	Correct	13 ms	1880 KB	Output is correct
23	Correct	13 ms	1972 KB	Output is correct
24	Correct	14 ms	1972 KB	Output is correct
25	Correct	15 ms	2008 KB	Output is correct
26	Correct	13 ms	2008 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	200 ms	8704 KB	Output is correct
2	Correct	198 ms	9864 KB	Output is correct
3	Correct	210 ms	10000 KB	Output is correct
4	Correct	201 ms	10000 KB	Output is correct
5	Correct	202 ms	10000 KB	Output is correct
6	Correct	616 ms	45472 KB	Output is correct
7	Correct	243 ms	45472 KB	Output is correct
8	Correct	304 ms	45472 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	45472 KB	Output is correct
2	Correct	308 ms	45472 KB	Output is correct
3	Correct	1360 ms	84472 KB	Output is correct
4	Correct	1317 ms	84480 KB	Output is correct
5	Correct	1218 ms	84480 KB	Output is correct
6	Correct	413 ms	84480 KB	Output is correct
7	Correct	187 ms	84480 KB	Output is correct
8	Correct	33 ms	84480 KB	Output is correct
9	Correct	1421 ms	84480 KB	Output is correct
10	Correct	1018 ms	84480 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1065 ms	84616 KB	Output is correct
2	Correct	1055 ms	84616 KB	Output is correct
3	Correct	360 ms	84616 KB	Output is correct
4	Correct	1037 ms	84616 KB	Output is correct
5	Correct	1307 ms	84616 KB	Output is correct
6	Correct	225 ms	84616 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	2 ms	372 KB	Output is correct
3	Correct	2 ms	448 KB	Output is correct
4	Correct	3 ms	652 KB	Output is correct
5	Correct	2 ms	652 KB	Output is correct
6	Correct	2 ms	652 KB	Output is correct
7	Correct	2 ms	652 KB	Output is correct
8	Correct	2 ms	652 KB	Output is correct
9	Correct	3 ms	652 KB	Output is correct
10	Correct	2 ms	652 KB	Output is correct
11	Correct	2 ms	652 KB	Output is correct
12	Correct	2 ms	652 KB	Output is correct
13	Correct	2 ms	652 KB	Output is correct
14	Correct	2 ms	652 KB	Output is correct
15	Correct	2 ms	652 KB	Output is correct
16	Correct	3 ms	652 KB	Output is correct
17	Correct	4 ms	652 KB	Output is correct
18	Correct	3 ms	652 KB	Output is correct
19	Correct	6 ms	732 KB	Output is correct
20	Correct	6 ms	732 KB	Output is correct
21	Correct	5 ms	748 KB	Output is correct
22	Correct	13 ms	1880 KB	Output is correct
23	Correct	13 ms	1972 KB	Output is correct
24	Correct	14 ms	1972 KB	Output is correct
25	Correct	15 ms	2008 KB	Output is correct
26	Correct	13 ms	2008 KB	Output is correct
27	Correct	9 ms	84616 KB	Output is correct
28	Correct	9 ms	84616 KB	Output is correct
29	Correct	8 ms	84616 KB	Output is correct
30	Correct	24 ms	84616 KB	Output is correct
31	Correct	27 ms	84616 KB	Output is correct
32	Correct	24 ms	84616 KB	Output is correct
33	Correct	69 ms	84616 KB	Output is correct
34	Correct	71 ms	84616 KB	Output is correct
35	Correct	79 ms	84616 KB	Output is correct
36	Correct	323 ms	84616 KB	Output is correct
37	Correct	308 ms	84616 KB	Output is correct
38	Correct	410 ms	84616 KB	Output is correct
39	Correct	322 ms	84616 KB	Output is correct
40	Correct	312 ms	84616 KB	Output is correct
41	Correct	308 ms	84616 KB	Output is correct
42	Correct	213 ms	84616 KB	Output is correct
43	Correct	270 ms	84616 KB	Output is correct
44	Correct	269 ms	84616 KB	Output is correct
45	Correct	244 ms	84616 KB	Output is correct
46	Correct	243 ms	84616 KB	Output is correct
47	Correct	226 ms	84616 KB	Output is correct
48	Correct	221 ms	84616 KB	Output is correct
49	Correct	228 ms	84616 KB	Output is correct
50	Correct	254 ms	84616 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	2 ms	372 KB	Output is correct
3	Correct	2 ms	448 KB	Output is correct
4	Correct	3 ms	652 KB	Output is correct
5	Correct	2 ms	652 KB	Output is correct
6	Correct	2 ms	652 KB	Output is correct
7	Correct	2 ms	652 KB	Output is correct
8	Correct	2 ms	652 KB	Output is correct
9	Correct	3 ms	652 KB	Output is correct
10	Correct	2 ms	652 KB	Output is correct
11	Correct	2 ms	652 KB	Output is correct
12	Correct	2 ms	652 KB	Output is correct
13	Correct	2 ms	652 KB	Output is correct
14	Correct	2 ms	652 KB	Output is correct
15	Correct	2 ms	652 KB	Output is correct
16	Correct	3 ms	652 KB	Output is correct
17	Correct	4 ms	652 KB	Output is correct
18	Correct	3 ms	652 KB	Output is correct
19	Correct	6 ms	732 KB	Output is correct
20	Correct	6 ms	732 KB	Output is correct
21	Correct	5 ms	748 KB	Output is correct
22	Correct	13 ms	1880 KB	Output is correct
23	Correct	13 ms	1972 KB	Output is correct
24	Correct	14 ms	1972 KB	Output is correct
25	Correct	15 ms	2008 KB	Output is correct
26	Correct	13 ms	2008 KB	Output is correct
27	Correct	200 ms	8704 KB	Output is correct
28	Correct	198 ms	9864 KB	Output is correct
29	Correct	210 ms	10000 KB	Output is correct
30	Correct	201 ms	10000 KB	Output is correct
31	Correct	202 ms	10000 KB	Output is correct
32	Correct	616 ms	45472 KB	Output is correct
33	Correct	243 ms	45472 KB	Output is correct
34	Correct	304 ms	45472 KB	Output is correct
35	Correct	2 ms	45472 KB	Output is correct
36	Correct	308 ms	45472 KB	Output is correct
37	Correct	1360 ms	84472 KB	Output is correct
38	Correct	1317 ms	84480 KB	Output is correct
39	Correct	1218 ms	84480 KB	Output is correct
40	Correct	413 ms	84480 KB	Output is correct
41	Correct	187 ms	84480 KB	Output is correct
42	Correct	33 ms	84480 KB	Output is correct
43	Correct	1421 ms	84480 KB	Output is correct
44	Correct	1018 ms	84480 KB	Output is correct
45	Correct	1065 ms	84616 KB	Output is correct
46	Correct	1055 ms	84616 KB	Output is correct
47	Correct	360 ms	84616 KB	Output is correct
48	Correct	1037 ms	84616 KB	Output is correct
49	Correct	1307 ms	84616 KB	Output is correct
50	Correct	225 ms	84616 KB	Output is correct
51	Correct	9 ms	84616 KB	Output is correct
52	Correct	9 ms	84616 KB	Output is correct
53	Correct	8 ms	84616 KB	Output is correct
54	Correct	24 ms	84616 KB	Output is correct
55	Correct	27 ms	84616 KB	Output is correct
56	Correct	24 ms	84616 KB	Output is correct
57	Correct	69 ms	84616 KB	Output is correct
58	Correct	71 ms	84616 KB	Output is correct
59	Correct	79 ms	84616 KB	Output is correct
60	Correct	323 ms	84616 KB	Output is correct
61	Correct	308 ms	84616 KB	Output is correct
62	Correct	410 ms	84616 KB	Output is correct
63	Correct	322 ms	84616 KB	Output is correct
64	Correct	312 ms	84616 KB	Output is correct
65	Correct	308 ms	84616 KB	Output is correct
66	Correct	213 ms	84616 KB	Output is correct
67	Correct	270 ms	84616 KB	Output is correct
68	Correct	269 ms	84616 KB	Output is correct
69	Correct	244 ms	84616 KB	Output is correct
70	Correct	243 ms	84616 KB	Output is correct
71	Correct	226 ms	84616 KB	Output is correct
72	Correct	221 ms	84616 KB	Output is correct
73	Correct	228 ms	84616 KB	Output is correct
74	Correct	254 ms	84616 KB	Output is correct
75	Correct	217 ms	84616 KB	Output is correct
76	Correct	215 ms	84616 KB	Output is correct
77	Correct	217 ms	84616 KB	Output is correct
78	Correct	207 ms	84616 KB	Output is correct
79	Correct	240 ms	84616 KB	Output is correct
80	Correct	216 ms	84616 KB	Output is correct
81	Correct	1233 ms	84616 KB	Output is correct
82	Correct	1293 ms	84616 KB	Output is correct
83	Correct	1202 ms	84616 KB	Output is correct
84	Correct	1310 ms	84780 KB	Output is correct
85	Correct	1161 ms	84780 KB	Output is correct
86	Correct	1221 ms	84780 KB	Output is correct
87	Correct	1230 ms	84780 KB	Output is correct
88	Correct	970 ms	84780 KB	Output is correct
89	Correct	990 ms	84780 KB	Output is correct
90	Correct	1000 ms	84780 KB	Output is correct
91	Correct	1022 ms	84780 KB	Output is correct
92	Correct	965 ms	84780 KB	Output is correct
93	Correct	1340 ms	84780 KB	Output is correct
94	Correct	1158 ms	84780 KB	Output is correct
95	Correct	1046 ms	84780 KB	Output is correct
96	Correct	1151 ms	84780 KB	Output is correct
97	Correct	1051 ms	84780 KB	Output is correct
98	Correct	622 ms	84780 KB	Output is correct
99	Correct	1200 ms	84780 KB	Output is correct
100	Correct	1164 ms	84780 KB	Output is correct
101	Correct	778 ms	84780 KB	Output is correct
102	Correct	1196 ms	84780 KB	Output is correct
103	Correct	1268 ms	84780 KB	Output is correct
104	Correct	1188 ms	84780 KB	Output is correct
105	Correct	771 ms	84780 KB	Output is correct
106	Correct	926 ms	84780 KB	Output is correct
107	Correct	966 ms	84780 KB	Output is correct
108	Correct	937 ms	84780 KB	Output is correct
109	Correct	986 ms	84780 KB	Output is correct
110	Correct	983 ms	84780 KB	Output is correct
111	Correct	1020 ms	84780 KB	Output is correct
112	Correct	991 ms	84780 KB	Output is correct
113	Correct	986 ms	84780 KB	Output is correct
114	Correct	1022 ms	84780 KB	Output is correct
115	Correct	964 ms	84780 KB	Output is correct
116	Correct	935 ms	84780 KB	Output is correct

답안 #87169

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 13.0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
13.0 / 13.0