Submission #773350

#TimeUsernameProblemLanguageResultExecution timeMemory
773350xetrkCircle selection (APIO18_circle_selection)C++14
87 / 100
3076 ms38844 KiB
#pragma warning(disable:4996) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; int n; vector<vector<ll>> circle; vector<pair<ll, int>> sortRadius, sortX, sortY; int skipX[300100], skipY[300100]; int xIdx[300100], yIdx[300100]; int ans[301000]; inline ll GetDist(ll x1, ll y1, ll x2, ll y2) { // 아 좌표값 마이너스도 들어오네 ll xx = max(x1, x2) - min(x1, x2); ll yy = max(y1, y2) - min(y1, y2); return (xx * xx) + (yy * yy); } bool comp(const pair<ll, int>& a, const pair<ll, int>& b) { if (a.first == b.first) return a.second < b.second; return a.first < b.first; } bool compSort(const pair<ll, int>& a, const pair<ll, int>& b) { if (a.first == b.first) return a.second < b.second; return a.first > b.first; } int main() { ll x, y, r, r2; int i; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lld %lld %lld", &x, &y, &r); //x = 1, y = 1, r = 3; circle.push_back({ x,y,r }); sortRadius.push_back({ r,i }); sortX.push_back({ x,i }); sortY.push_back({ y,i }); skipX[i] = i + 1; skipY[i] = i + 1; } sort(sortRadius.begin(), sortRadius.end(), compSort); sort(sortX.begin(), sortX.end()); sort(sortY.begin(), sortY.end()); for (int i = 0; i < n; i++) { xIdx[sortX[i].second] = i; yIdx[sortY[i].second] = i; } int cur, curcmp; int xMin, xMax, yMin, yMax; int next; ll rr; fill(ans, ans + n + 2, -1); for (int curDelete = 0; curDelete < n; curDelete++) { cur = sortRadius[curDelete].second; if (ans[cur] != -1) continue; x = circle[cur][0], y = circle[cur][1], r = circle[cur][2]; if (curDelete < n - 1) r2 = r + sortRadius[curDelete + 1].first + 1; else r2 = r * 2 + 1; // a이하를 찾아야하는데 lower bound는 a이상인걸 찾으니까.. 근데 그 이하인걸 찾아야하니 1빼줌 xMin = lower_bound(sortX.begin(), sortX.end(), pair<ll, int>(x - r2, -1), comp) - sortX.begin(); xMax = upper_bound(sortX.begin(), sortX.end(), pair<ll, int>(x + r2, 301000), comp) - sortX.begin(); yMin = lower_bound(sortY.begin(), sortY.end(), pair<ll, int>(y - r2, -1), comp) - sortY.begin(); yMax = upper_bound(sortY.begin(), sortY.end(), pair<ll, int>(y + r2, 301000), comp) - sortY.begin(); xMin--; yMin--; if (xMin < 0) xMin = 0; if (yMin < 0) yMin = 0; if (xMin >= sortX.size()) xMin = sortX.size() - 1; if (yMin >= sortY.size()) yMin = sortY.size() - 1; if (xMax >= sortX.size()) xMax = sortX.size() - 1; if (yMax >= sortY.size()) yMax = sortY.size() - 1; //xMin = 0, yMin = 0, xMax = n - 1, yMax = n - 1; ans[cur] = cur; if (xIdx[cur] - 1 >= 0) { skipX[xIdx[cur] - 1] = skipX[xIdx[cur]]; if (skipX[xIdx[cur] - 1] == 0) skipX[xIdx[cur] - 1] = n + 1; } if (yIdx[cur] - 1 >= 0) { skipY[yIdx[cur] - 1] = skipY[yIdx[cur]]; if (skipY[yIdx[cur] - 1] == 0) skipY[yIdx[cur] - 1] = n + 1; } //xIdx[cur] if (xMax - xMin < yMax - yMin) { i = xMin; while (i <= xMax) { curcmp = sortX[i].second; next = skipX[i]; if (ans[curcmp] != -1) { i = next; continue; } rr = r + circle[curcmp][2]; if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr) { ans[curcmp] = cur; //sortX.erase(sortX.begin() + i); if (i - 1 >= 0) skipX[i - 1] = skipX[i]; if (yIdx[curcmp] - 1 >= 0) { skipY[yIdx[curcmp] - 1] = skipY[yIdx[curcmp]]; if (skipY[yIdx[curcmp] - 1] == 0) skipY[yIdx[curcmp] - 1] = n + 1; } } i = next; } } else { i = yMin; while (i <= yMax) { curcmp = sortY[i].second; next = skipY[i]; if (ans[curcmp] != -1) { i = next; continue; } rr = r + circle[curcmp][2]; if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr) { ans[curcmp] = cur; //sortX.erase(sortX.begin() + i); if (i - 1>= 0) skipY[i - 1] = skipY[i]; if (xIdx[curcmp] - 1 >= 0) { skipX[xIdx[curcmp] - 1] = skipX[xIdx[curcmp]]; if (skipX[xIdx[curcmp] - 1] == 0) skipX[xIdx[curcmp] - 1] = n + 1; } } i = next; } /* for (int i = yMax; i >= yMin; i--) { curcmp = sortY[i].second; if (ans[curcmp]!= -1) continue; rr = r + circle[curcmp][2]; if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr) { ans[curcmp] = cur; //sortY.erase(sortY.begin() + i); } }*/ } } for (int i = 0; i < n; i++) printf("%d ", ans[i] + 1); return 0; }

Compilation message (stderr)

circle_selection.cpp:1: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    1 | #pragma warning(disable:4996)
      | 
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         if (xMin >= sortX.size()) xMin = sortX.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         if (yMin >= sortY.size()) yMin = sortY.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         if (xMax >= sortX.size()) xMax = sortX.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         if (yMax >= sortY.size()) yMax = sortY.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%lld %lld %lld", &x, &y, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...