oj.uz

Submission #204931

# Submission time Handle Problem Language Result Execution time Memory
204931 2020-02-27T13:30:10 Z oolimry Circle selection (APIO18_circle_selection) C++14
12 / 100
 3000 ms 285472 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, long long> ii;

int n; 

struct Circle{
  long long x, y, r, id;
} sorted[300005], arr[300005];;

bool intersect(Circle a, Circle 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);
}

long long ans[300005];

struct pair_hash{
  std::size_t operator () (ii const &pair) const{
    return pair.first ^ pair.second;
  }
};

unordered_map<ii, vector<int>, pair_hash> GRID;
long long gridSize = 1LL << 61LL;

void buildGrid(long long newGridSize){
  gridSize = newGridSize;
  GRID.clear();

  for(int i = 0;i < n;i++){
    if(ans[i] == -1){
      long long xSquare = arr[i].x / gridSize;
      long long ySquare = arr[i].y / gridSize;
      GRID[ii(xSquare,ySquare)].push_back(i);
    }
  }
}

bool comp(Circle a, Circle b){
  if(a.r == b.r) return a.id < b.id;
  else return a.r > b.r;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  fill(ans, ans + n, -1);

  for(int i = 0;i < n;i++){
    long long x, y, r; cin >> x >> y >> r;
    x += (1LL << 31LL); y += (1LL << 31LL);
    arr[i] = {x, y, r, i};
    sorted[i] = {x, y, r, i};
  }

  sort(sorted,sorted+n,comp);

  for(int i = 0;i < n;i++){
    Circle C = sorted[i];

    if(ans[C.id] != -1) continue;
    //ans[C.id] = C.id;

    if(gridSize > 2 * C.r){
      buildGrid(C.r);
    }

    long long xSquare = C.x / gridSize;
    long long ySquare = C.y / gridSize;

    for(long long x = xSquare - 2;x <= xSquare + 2;x++){
      for(long long y = ySquare - 2;y < ySquare + 2;y++){
        vector<int> &points = GRID[ii(x,y)];

        for(int p = 0;p < (int) points.size();p++){
          if(intersect(arr[points[p]],C)){
            ans[points[p]] = C.id;

            points[p] = points.back();
            points.pop_back();
            p--;
          }
        }
      }
    }
  }

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 380 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 248 KB Output is correct
8 Incorrect 5 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 24148 KB Output is correct
2 Correct 212 ms 23820 KB Output is correct
3 Correct 221 ms 25016 KB Output is correct
4 Correct 208 ms 23744 KB Output is correct
5 Correct 252 ms 27564 KB Output is correct
6 Correct 991 ms 79724 KB Output is correct
7 Correct 291 ms 30860 KB Output is correct
8 Correct 411 ms 38840 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Execution timed out 3079 ms 89824 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3082 ms 285472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 380 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 248 KB Output is correct
8 Incorrect 5 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 380 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 248 KB Output is correct
8 Incorrect 5 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -