oj.uz

Submission #655732

# Submission time Handle Problem Language Result Execution time Memory
655732 2022-11-05T11:52:04 Z Richem Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 460752 KB 
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
 
const int MAX_ALED = 3e5+42, MAX_POS = 1e9;
 
struct Aled{
    unsigned long long xCentre, yCentre, rayon, id;
 
    bool ragequit = false;
 
    bool intersecte(Aled autre) {
        unsigned long long x = xCentre - autre.xCentre, y = yCentre - autre.yCentre;
        unsigned long long xCarre = x*x, yCarre = y*y, rayonCarre = (rayon + autre.rayon) * (rayon + autre.rayon);
        return xCarre + yCarre <= rayonCarre;
    }
    bool operator<(Aled autre) {
        if(rayon == autre.rayon)
            return id < autre.id;
        return rayon > autre.rayon;
    }
};
 
struct Position{
    long long int x,y;
 
    unsigned long long int getId() {
        return (x << 32) + y;
    }
};
 
int nbAled;
Aled aled[MAX_ALED];
Aled triRayon[MAX_ALED];
 
void input() {
    cin >> nbAled;
 
    for(int iAled = 0; iAled < nbAled; iAled++) {
        cin >> aled[iAled].xCentre >> aled[iAled].yCentre >> aled[iAled].rayon;
        aled[iAled].xCentre += MAX_POS;
        aled[iAled].yCentre += MAX_POS;
        aled[iAled].id = iAled;
    }
    sort(aled, aled + nbAled);
}
 
unordered_map<long long int, vector<int>> enfer;
Position quelCase[MAX_ALED];
 
void calcGrille(int taille) {
    enfer.clear();
    for(int cur = 0; cur < nbAled; cur++) {
        int xCase = aled[cur].xCentre / taille, yCase = aled[cur].yCentre / taille;
 
        Position caseCur = {xCase, yCase};
 
        enfer[caseCur.getId()].push_back(cur);
        quelCase[cur] = {xCase, yCase};
    }
}
 
bool retire[MAX_ALED] = {0};
int rep[MAX_ALED];
 
int tailleGrille;
 
int main() {
    input();
    tailleGrille = (1 << 30);

    for(int curCercle = 0; curCercle < nbAled; curCercle++) {
        if(retire[curCercle])
            continue;
 
        while(aled[curCercle].rayon < tailleGrille) {
            tailleGrille /= 2;
            calcGrille(tailleGrille);
        }

        for(int deltaX = -3; deltaX <= 3; deltaX++) {
            for(int deltaY = -3; deltaY <= 3; deltaY++) {
                int xCaseNouv = quelCase[curCercle].x + deltaX, yCaseNouv = quelCase[curCercle].y + deltaY;
                Position caseNouv = {xCaseNouv, yCaseNouv};

                if(xCaseNouv < 0 || yCaseNouv < 0)
                    continue;
 
                for(auto autreCercle : enfer[caseNouv.getId()]) {
                    if(!retire[autreCercle] && aled[curCercle].intersecte(aled[autreCercle])) {
                        retire[autreCercle] = 1;
                        rep[aled[autreCercle].id] = aled[curCercle].id+1;
                    }
                }
            }
        }
    }
 
    for(int curCercle = 0; curCercle < nbAled; curCercle++) {
        cout << rep[curCercle] << " ";
    }
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:78:37: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   78 |         while(aled[curCercle].rayon < tailleGrille) {
      |               ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23764 KB Output is correct
2 Correct 9 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 9 ms 23772 KB Output is correct
5 Correct 10 ms 23800 KB Output is correct
6 Correct 9 ms 23764 KB Output is correct
7 Correct 9 ms 23800 KB Output is correct
8 Correct 10 ms 23796 KB Output is correct
9 Correct 9 ms 23764 KB Output is correct
10 Correct 10 ms 23796 KB Output is correct
11 Correct 10 ms 23892 KB Output is correct
12 Correct 9 ms 23892 KB Output is correct
13 Correct 10 ms 23892 KB Output is correct
14 Correct 10 ms 23892 KB Output is correct
15 Correct 10 ms 23892 KB Output is correct
16 Correct 12 ms 23932 KB Output is correct
17 Incorrect 11 ms 23756 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 34484 KB Output is correct
2 Incorrect 379 ms 40564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23764 KB Output is correct
2 Incorrect 2485 ms 149952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23764 KB Output is correct
2 Correct 9 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 9 ms 23772 KB Output is correct
5 Correct 10 ms 23800 KB Output is correct
6 Correct 9 ms 23764 KB Output is correct
7 Correct 9 ms 23800 KB Output is correct
8 Correct 10 ms 23796 KB Output is correct
9 Correct 9 ms 23764 KB Output is correct
10 Correct 10 ms 23796 KB Output is correct
11 Correct 10 ms 23892 KB Output is correct
12 Correct 9 ms 23892 KB Output is correct
13 Correct 10 ms 23892 KB Output is correct
14 Correct 10 ms 23892 KB Output is correct
15 Correct 10 ms 23892 KB Output is correct
16 Correct 12 ms 23932 KB Output is correct
17 Incorrect 11 ms 23756 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23764 KB Output is correct
2 Correct 9 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 9 ms 23772 KB Output is correct
5 Correct 10 ms 23800 KB Output is correct
6 Correct 9 ms 23764 KB Output is correct
7 Correct 9 ms 23800 KB Output is correct
8 Correct 10 ms 23796 KB Output is correct
9 Correct 9 ms 23764 KB Output is correct
10 Correct 10 ms 23796 KB Output is correct
11 Correct 10 ms 23892 KB Output is correct
12 Correct 9 ms 23892 KB Output is correct
13 Correct 10 ms 23892 KB Output is correct
14 Correct 10 ms 23892 KB Output is correct
15 Correct 10 ms 23892 KB Output is correct
16 Correct 12 ms 23932 KB Output is correct
17 Incorrect 11 ms 23756 KB Output isn't correct
18 Halted 0 ms 0 KB -