제출 #625125

#제출 시각아이디문제언어결과실행 시간메모리
625125jjang36524원 고르기 (APIO18_circle_selection)C++14
64 / 100
3102 ms43000 KiB
#include <iostream> #include <algorithm> #include <unordered_map> #include <vector> #define int long long using namespace std; unordered_map<int, vector<int>>x; int po[300100][2]; vector<pair<int, int>>so; int pre[300100]; int num[300100]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int i; for (i = 0; i < N; i++) { int a, b, c; cin >> a >> b >> c; a += 1LL << 30; b += 1LL << 30; pre[i] = c; so.push_back({ -c,i }); po[i][0] = a; po[i][1] = b; } sort(so.begin(), so.end()); int gr = 30; for (i = 0; i < N; i++) { x[po[i][0] / (1LL << gr) * (1LL << 31) + po[i][1] / (1LL << gr)].push_back(i); } for (i = 0; i < N; i++) { if (num[so[i].second]) continue; while ((1LL << gr) >= -so[i].first * 2) { gr--; x.clear(); int i; for (i = 0; i < N; i++) { if (num[i]) continue; x[po[i][0] / (1LL << gr) * (1LL << 31) + po[i][1] / (1LL << gr)].push_back(i); } } int cuuu = so[i].second; int xx = po[cuuu][0] / (1LL << gr); int y = po[cuuu][1] / (1LL << gr); int j, k; for (j = xx - 2; j <= xx + 2; j++) { for (k = y - 2; k <= y + 2; k++) { int v=(j<<31)+k; if (!x.count(j * (1LL << 31) + k)) continue; for (auto l = x[v].begin(); l != x[v].end(); l++) { int le = *l; if (num[le]) continue; int xxx = (po[cuuu][0] - po[le][0]); int yyy = (po[cuuu][1] - po[le][1]); int rrr = (-so[i].first + pre[le]); if (xxx * xxx + yyy * yyy <= rrr * rrr) { num[le] = cuuu + 1; } } } } } for (i = 0; i < N; i++) { cout << num[i] << ' '; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...