oj.uz

Submission #658188

# Submission time Handle Problem Language Result Execution time Memory
658188 2022-11-12T11:01:52 Z Richem Circle selection (APIO18_circle_selection) C++14
19 / 100
 3000 ms 557632 KB 
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
#define int long long

using namespace std;

const int MAX_CERCLE = 3e5+42, INF = 1e9;

struct Cercle{
    int xCentre, yCentre, rayon, id;

    bool operator<(Cercle autre) {
        if(rayon == autre.rayon)
            return id < autre.id;
        return rayon > autre.rayon;
    }

    bool intersecte(Cercle autre) {
        int xDist = xCentre - autre.xCentre, yDist = yCentre - autre.yCentre;
        int rDist = rayon + autre.rayon;

        return xDist * xDist + yDist * yDist <= rDist * rDist;
    }
};

int nbCercle;
Cercle cercle[MAX_CERCLE];

void input() {
    cin >> nbCercle;

    for(int idCercle = 0; idCercle < nbCercle; idCercle++) {
        cin >> cercle[idCercle].xCentre >> cercle[idCercle].yCentre >> cercle[idCercle].rayon;
        cercle[idCercle].xCentre += INF;
        cercle[idCercle].yCentre += INF;
        cercle[idCercle].id = idCercle;
    }
    sort(cercle, cercle + nbCercle);
}

unordered_map<int, vector<int>> grille;
bool enleve[MAX_CERCLE] = {0};

void ajoutCercleGrille(int idCercle, int taille) {
    if(enleve[idCercle])
        return;
    int xGrille = cercle[idCercle].xCentre / taille, yGrille = cercle[idCercle].yCentre / taille;
    
    grille[(xGrille << 32) + yGrille].push_back(idCercle);
}

void calcGrille(int taille) {
    for(int cur = 0; cur < nbCercle; cur++) {
        ajoutCercleGrille(cur, taille);
    }
}

int quiEnleve[MAX_CERCLE];

int tailleGrille = (1e12);

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    input();

    for(int grand = 0; grand < nbCercle; grand++) {
        if(enleve[grand])
            continue;

        while(tailleGrille/2 > cercle[grand].rayon) {
            tailleGrille /= 2;
            calcGrille(tailleGrille);
        }

        int xGrille = cercle[grand].xCentre / tailleGrille, yGrille = cercle[grand].yCentre / tailleGrille;

        vector<int> quiReste;
        for(int type = 0; type < 2; type++) {
            for(int deltaX = -4; deltaX <= 4; deltaX++) {
                for(int deltaY = -4; deltaY <= 4; deltaY++) {
                    int nouvX = xGrille + deltaX, nouvY = yGrille + deltaY;

                    if(type == 1) {
                        grille[(nouvX << 32) + nouvY].clear();
                        continue;
                    }

                    for(auto autre : grille[(nouvX << 32) + nouvY]) {
                        if(cercle[grand].intersecte(cercle[autre]) && !enleve[autre]) {
                            enleve[autre] = 1;
                            quiEnleve[cercle[autre].id] = cercle[grand].id;
                        }
                        if(!cercle[grand].intersecte(cercle[autre])) {
                            quiReste.push_back(autre);
                        }
                    }
                }
            }
        }

        for(auto nouveau : quiReste) {
            ajoutCercleGrille(nouveau, tailleGrille);
        }
    }

    for(int cur = 0; cur < nbCercle; cur++) {
        cout << quiEnleve[cur]+1 << " ";
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 2 ms 560 KB Output is correct
17 Correct 1 ms 552 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 4 ms 1240 KB Output is correct
20 Correct 4 ms 1252 KB Output is correct
21 Correct 5 ms 1480 KB Output is correct
22 Correct 153 ms 29692 KB Output is correct
23 Correct 127 ms 29432 KB Output is correct
24 Correct 118 ms 29264 KB Output is correct
25 Correct 125 ms 30560 KB Output is correct
26 Correct 154 ms 29796 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 45344 KB Output is correct
2 Correct 334 ms 83344 KB Output is correct
3 Correct 274 ms 56300 KB Output is correct
4 Correct 239 ms 42800 KB Output is correct
5 Correct 616 ms 114300 KB Output is correct
6 Correct 2946 ms 380284 KB Output is correct
7 Correct 804 ms 130628 KB Output is correct
8 Correct 1121 ms 180300 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 3096 ms 514928 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 3113 ms 556892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 2 ms 560 KB Output is correct
17 Correct 1 ms 552 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 4 ms 1240 KB Output is correct
20 Correct 4 ms 1252 KB Output is correct
21 Correct 5 ms 1480 KB Output is correct
22 Correct 153 ms 29692 KB Output is correct
23 Correct 127 ms 29432 KB Output is correct
24 Correct 118 ms 29264 KB Output is correct
25 Correct 125 ms 30560 KB Output is correct
26 Correct 154 ms 29796 KB Output is correct
27 Correct 8 ms 1748 KB Output is correct
28 Correct 8 ms 1864 KB Output is correct
29 Correct 9 ms 1748 KB Output is correct
30 Correct 311 ms 57976 KB Output is correct
31 Correct 319 ms 57764 KB Output is correct
32 Correct 340 ms 58624 KB Output is correct
33 Correct 72 ms 13752 KB Output is correct
34 Correct 91 ms 13792 KB Output is correct
35 Correct 96 ms 27036 KB Output is correct
36 Execution timed out 3097 ms 557632 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 2 ms 560 KB Output is correct
17 Correct 1 ms 552 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 4 ms 1240 KB Output is correct
20 Correct 4 ms 1252 KB Output is correct
21 Correct 5 ms 1480 KB Output is correct
22 Correct 153 ms 29692 KB Output is correct
23 Correct 127 ms 29432 KB Output is correct
24 Correct 118 ms 29264 KB Output is correct
25 Correct 125 ms 30560 KB Output is correct
26 Correct 154 ms 29796 KB Output is correct
27 Correct 227 ms 45344 KB Output is correct
28 Correct 334 ms 83344 KB Output is correct
29 Correct 274 ms 56300 KB Output is correct
30 Correct 239 ms 42800 KB Output is correct
31 Correct 616 ms 114300 KB Output is correct
32 Correct 2946 ms 380284 KB Output is correct
33 Correct 804 ms 130628 KB Output is correct
34 Correct 1121 ms 180300 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Execution timed out 3096 ms 514928 KB Time limit exceeded
37 Halted 0 ms 0 KB -