oj.uz

Submission #658203

# Submission time Handle Problem Language Result Execution time Memory
658203 2022-11-12T11:33:31 Z Richem Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 531396 KB 
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

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

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

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

    bool intersecte(Cercle autre) {
        long long xDist = xCentre - autre.xCentre, yDist = yCentre - autre.yCentre;
        long long 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<long long, vector<int>> grille;
bool enleve[MAX_CERCLE] = {0};

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

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

int quiEnleve[MAX_CERCLE];

long long tailleGrille = (1e12);

int 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);
        }

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

        vector<int> quiReste;
        for(int type = 0; type < 2; type++) {
            for(int deltaX = -2; deltaX <= 2; deltaX++) {
                for(int deltaY = -2; deltaY <= 2; deltaY++) {
                    long long 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 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 4 ms 856 KB Output is correct
20 Correct 4 ms 856 KB Output is correct
21 Correct 5 ms 940 KB Output is correct
22 Correct 43 ms 11576 KB Output is correct
23 Correct 45 ms 11464 KB Output is correct
24 Correct 47 ms 11376 KB Output is correct
25 Correct 72 ms 15040 KB Output is correct
26 Correct 43 ms 11844 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 28084 KB Output is correct
2 Correct 309 ms 47796 KB Output is correct
3 Correct 243 ms 28996 KB Output is correct
4 Correct 217 ms 26176 KB Output is correct
5 Correct 534 ms 61980 KB Output is correct
6 Correct 1899 ms 182676 KB Output is correct
7 Correct 584 ms 66792 KB Output is correct
8 Correct 771 ms 90564 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 Correct 1560 ms 187316 KB Output is correct
3 Execution timed out 3069 ms 509724 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
30.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 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 4 ms 856 KB Output is correct
20 Correct 4 ms 856 KB Output is correct
21 Correct 5 ms 940 KB Output is correct
22 Correct 43 ms 11576 KB Output is correct
23 Correct 45 ms 11464 KB Output is correct
24 Correct 47 ms 11376 KB Output is correct
25 Correct 72 ms 15040 KB Output is correct
26 Correct 43 ms 11844 KB Output is correct
27 Correct 9 ms 1240 KB Output is correct
28 Correct 8 ms 1296 KB Output is correct
29 Correct 7 ms 1236 KB Output is correct
30 Correct 118 ms 22168 KB Output is correct
31 Correct 115 ms 21944 KB Output is correct
32 Correct 127 ms 22980 KB Output is correct
33 Correct 76 ms 8936 KB Output is correct
34 Correct 75 ms 9096 KB Output is correct
35 Correct 82 ms 10036 KB Output is correct
36 Correct 2063 ms 245648 KB Output is correct
37 Correct 2155 ms 247940 KB Output is correct
38 Correct 2029 ms 243836 KB Output is correct
39 Correct 841 ms 35264 KB Output is correct
40 Correct 837 ms 35288 KB Output is correct
41 Correct 783 ms 35260 KB Output is correct
42 Correct 255 ms 27036 KB Output is correct
43 Correct 1498 ms 164716 KB Output is correct
44 Correct 1350 ms 164992 KB Output is correct
45 Correct 1503 ms 164968 KB Output is correct
46 Correct 1427 ms 165196 KB Output is correct
47 Correct 1331 ms 165040 KB Output is correct
48 Correct 1382 ms 165272 KB Output is correct
49 Correct 1417 ms 165144 KB Output is correct
50 Correct 1730 ms 164964 KB Output is correct

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 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 4 ms 856 KB Output is correct
20 Correct 4 ms 856 KB Output is correct
21 Correct 5 ms 940 KB Output is correct
22 Correct 43 ms 11576 KB Output is correct
23 Correct 45 ms 11464 KB Output is correct
24 Correct 47 ms 11376 KB Output is correct
25 Correct 72 ms 15040 KB Output is correct
26 Correct 43 ms 11844 KB Output is correct
27 Correct 228 ms 28084 KB Output is correct
28 Correct 309 ms 47796 KB Output is correct
29 Correct 243 ms 28996 KB Output is correct
30 Correct 217 ms 26176 KB Output is correct
31 Correct 534 ms 61980 KB Output is correct
32 Correct 1899 ms 182676 KB Output is correct
33 Correct 584 ms 66792 KB Output is correct
34 Correct 771 ms 90564 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1560 ms 187316 KB Output is correct
37 Execution timed out 3069 ms 509724 KB Time limit exceeded
38 Halted 0 ms 0 KB -