# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
49137 | 2018-05-22T16:09:38 Z | BThero | 원 고르기 (APIO18_circle_selection) | C++17 | 3000 ms | 41400 KB |
// Why am I so stupid? :c #include <bits/stdc++.h> #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define fi first #define se second typedef long long ll; using namespace std; struct circle { int x, y, r, id; circle() { x = y = r = id = 0; } } arr[300005]; map < ll, vector <int> > mm; int ans[300005]; int u[300005]; int n, cur; int block; bool inter(circle a, circle b) { ll dist = (a.x - b.x) * 1ll * (a.x - b.x) + (a.y - b.y) * 1ll * (a.y - b.y); return dist <= (a.r + b.r) * 1ll * (a.r + b.r); } bool cmp(circle a, circle b) { if (a.r == b.r) { return a.id < b.id; } return a.r > b.r; } ll f(int x, int y) { return x * (ll)2e9 + y; } void divIntoBlocks(int st) { mm.clear(); for (int i = st; i <= n; ++i) { mm[f(arr[i].x / block, arr[i].y / block)].pb(i); } } void solve() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d %d %d", &arr[i].x, &arr[i].y, &arr[i].r); arr[i].id = i; } sort(arr + 1, arr + n + 1, cmp); for (int i = 1; i <= n; ++i) { ans[i] = i; } for (int i = 1; i <= n; ++i) { if (ans[arr[i].id] != arr[i].id) { continue; } if (arr[i].r != block) { block = arr[i].r; divIntoBlocks(i + 1); } int cx = arr[i].x / block; int cy = arr[i].y / block; for (int x = cx - 2; x <= cx + 2; ++x) { for (int y = cy - 2; y <= cy + 2; ++y) { ll cur = f(x, y); auto P = mm.find(cur); if (P != mm.end()) { for (int it : P -> se) { if (inter(arr[i], arr[it])) { ans[arr[it].id] = arr[i].id; } } vector <int> vv; for (int it : P -> se) { if (ans[arr[it].id] == arr[it].id) { vv.pb(it); } } P -> se = vv; } } } } for (int i = 1; i <= n; ++i) { printf("%d ", ans[i]); } } int main() { #ifdef BThero freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // BThero int tt = 1; while (tt--) { solve(); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 5092 KB | Output is correct |
3 | Correct | 7 ms | 5092 KB | Output is correct |
4 | Correct | 5 ms | 5144 KB | Output is correct |
5 | Correct | 7 ms | 5332 KB | Output is correct |
6 | Correct | 6 ms | 5332 KB | Output is correct |
7 | Correct | 5 ms | 5332 KB | Output is correct |
8 | Incorrect | 6 ms | 5332 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 211 ms | 8908 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 8908 KB | Output is correct |
2 | Execution timed out | 3054 ms | 16648 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2291 ms | 41308 KB | Output is correct |
2 | Correct | 1606 ms | 41308 KB | Output is correct |
3 | Correct | 752 ms | 41308 KB | Output is correct |
4 | Correct | 1709 ms | 41328 KB | Output is correct |
5 | Correct | 1688 ms | 41400 KB | Output is correct |
6 | Correct | 402 ms | 41400 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 5092 KB | Output is correct |
3 | Correct | 7 ms | 5092 KB | Output is correct |
4 | Correct | 5 ms | 5144 KB | Output is correct |
5 | Correct | 7 ms | 5332 KB | Output is correct |
6 | Correct | 6 ms | 5332 KB | Output is correct |
7 | Correct | 5 ms | 5332 KB | Output is correct |
8 | Incorrect | 6 ms | 5332 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 5092 KB | Output is correct |
3 | Correct | 7 ms | 5092 KB | Output is correct |
4 | Correct | 5 ms | 5144 KB | Output is correct |
5 | Correct | 7 ms | 5332 KB | Output is correct |
6 | Correct | 6 ms | 5332 KB | Output is correct |
7 | Correct | 5 ms | 5332 KB | Output is correct |
8 | Incorrect | 6 ms | 5332 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |