oj.uz

Submission #391059

# Submission time Handle Problem Language Result Execution time Memory
391059 2021-04-17T17:26:03 Z phathnv Circle selection (APIO18_circle_selection) C++11
0 / 100
 767 ms 32160 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 3e5 + 7;

struct Circle{
    int x, y, r;
};

int n, answer[N], ord[N], ordX[N], numRow, inRow[N];
vector<int> row[N];
Circle c[N];

bool Intersect(const Circle &c1, const Circle &c2){
    int dx = c1.x - c2.x;
    int dy = c1.y - c2.y;
    int sr = c1.r + c2.r;
    return (ll) dx * dx + (ll) dy * dy <= (ll) sr * sr;
}

void Rebuild(int k){
    for(int i = 1; i <= numRow; i++)
        row[i].clear();

    numRow = 0;
    int last = -1;
    for(int i = 1; i <= n; i++){
        int ind = ordX[i];
        if (answer[ind])
            continue;
        if ((c[ind].x >> k) != last){
            last = c[ind].x >> k;
            numRow++;
        }
        row[numRow].push_back(ind);
        inRow[ind] = numRow;
    }
    for(int i = 1; i <= numRow; i++)
        sort(row[i].begin(), row[i].end(), [&](const int &a, const int &b){
                return (c[a].y >> k) < (c[b].y >> k);
             });
}

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

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> c[i].x >> c[i].y >> c[i].r;
        c[i].x += 1e9;
        c[i].y += 1e9;
        ord[i] = i;
        ordX[i] = i;
    }

    sort(ord + 1, ord + 1 + n, [&](const int &a, const int &b){
            if (c[a].r != c[b].r)
                return c[a].r > c[b].r;
            return a < b;
         });
    sort(ordX + 1, ordX + 1 + n, [&](const int &a, const int &b){
            return c[a].x < c[b].x;
         });
    int k = 30;
    for(int i = 1; i <= n; i++){
        int ind = ord[i];
        if (answer[ind])
            continue;
        while (c[ind].r < (1 << k))
            Rebuild(--k);
        for(int x = max(1, inRow[ind] - 2); x <= min(numRow, inRow[ind] + 2); x++){
            if (abs((c[row[x][0]].x >> k) - (c[ind].x >> k)) > 2)
                continue;
            int l = 0, r = row[x].size() - 1, p = row[x].size();
            while (l <= r){
                int mid = (l + r) >> 1;
                if ((c[row[x][mid]].y >> k) >= (c[ind].y >> k) - 2){
                    p = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            while (p < (int) row[x].size()){
                if (Intersect(c[ind], c[row[x][p]]) && !answer[row[x][p]])
                    answer[row[x][p]] = ind;
                if ((c[row[x][p]].y >> k) > (c[ind].y >> k) + 2)
                    break;
                p++;
            }
         }
    }

    for(int i = 1; i <= n; i++)
        cout << answer[i] << ' ';

    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 4 ms 7320 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 4 ms 7376 KB Output is correct
11 Correct 5 ms 7372 KB Output is correct
12 Correct 4 ms 7372 KB Output is correct
13 Correct 6 ms 7376 KB Output is correct
14 Correct 5 ms 7372 KB Output is correct
15 Correct 5 ms 7372 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Incorrect 6 ms 7372 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 19832 KB Output is correct
2 Incorrect 262 ms 20180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Incorrect 184 ms 14384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 767 ms 32160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 4 ms 7320 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 4 ms 7376 KB Output is correct
11 Correct 5 ms 7372 KB Output is correct
12 Correct 4 ms 7372 KB Output is correct
13 Correct 6 ms 7376 KB Output is correct
14 Correct 5 ms 7372 KB Output is correct
15 Correct 5 ms 7372 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Incorrect 6 ms 7372 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 4 ms 7320 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 4 ms 7376 KB Output is correct
11 Correct 5 ms 7372 KB Output is correct
12 Correct 4 ms 7372 KB Output is correct
13 Correct 6 ms 7376 KB Output is correct
14 Correct 5 ms 7372 KB Output is correct
15 Correct 5 ms 7372 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Incorrect 6 ms 7372 KB Output isn't correct
18 Halted 0 ms 0 KB -