oj.uz

Submission #655736

# Submission time Handle Problem Language Result Execution time Memory
655736 2022-11-05T11:59:04 Z Richem Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 317112 KB 
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#define int long long
using namespace std;
 
const int MAX_ALED = 3e5+42, MAX_POS = 1e9;
 
struct Aled{
    int xCentre, yCentre, rayon, id;
 
    bool ragequit = false;
 
    bool intersecte(Aled autre) {
        int x = xCentre - autre.xCentre, y = yCentre - autre.yCentre;
        int 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{
    int x,y;
 
    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<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;
 
signed 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] << " ";
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23716 KB Output is correct
2 Correct 12 ms 23776 KB Output is correct
3 Correct 11 ms 23768 KB Output is correct
4 Correct 9 ms 23784 KB Output is correct
5 Correct 9 ms 23764 KB Output is correct
6 Correct 9 ms 23764 KB Output is correct
7 Correct 9 ms 23764 KB Output is correct
8 Correct 9 ms 23764 KB Output is correct
9 Correct 9 ms 23780 KB Output is correct
10 Correct 11 ms 23720 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 10 ms 23896 KB Output is correct
13 Correct 11 ms 23892 KB Output is correct
14 Correct 11 ms 23892 KB Output is correct
15 Correct 13 ms 23892 KB Output is correct
16 Correct 12 ms 23920 KB Output is correct
17 Incorrect 14 ms 23764 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 37824 KB Output is correct
2 Incorrect 392 ms 36772 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 2500 ms 147548 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 3080 ms 317112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23716 KB Output is correct
2 Correct 12 ms 23776 KB Output is correct
3 Correct 11 ms 23768 KB Output is correct
4 Correct 9 ms 23784 KB Output is correct
5 Correct 9 ms 23764 KB Output is correct
6 Correct 9 ms 23764 KB Output is correct
7 Correct 9 ms 23764 KB Output is correct
8 Correct 9 ms 23764 KB Output is correct
9 Correct 9 ms 23780 KB Output is correct
10 Correct 11 ms 23720 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 10 ms 23896 KB Output is correct
13 Correct 11 ms 23892 KB Output is correct
14 Correct 11 ms 23892 KB Output is correct
15 Correct 13 ms 23892 KB Output is correct
16 Correct 12 ms 23920 KB Output is correct
17 Incorrect 14 ms 23764 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23716 KB Output is correct
2 Correct 12 ms 23776 KB Output is correct
3 Correct 11 ms 23768 KB Output is correct
4 Correct 9 ms 23784 KB Output is correct
5 Correct 9 ms 23764 KB Output is correct
6 Correct 9 ms 23764 KB Output is correct
7 Correct 9 ms 23764 KB Output is correct
8 Correct 9 ms 23764 KB Output is correct
9 Correct 9 ms 23780 KB Output is correct
10 Correct 11 ms 23720 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 10 ms 23896 KB Output is correct
13 Correct 11 ms 23892 KB Output is correct
14 Correct 11 ms 23892 KB Output is correct
15 Correct 13 ms 23892 KB Output is correct
16 Correct 12 ms 23920 KB Output is correct
17 Incorrect 14 ms 23764 KB Output isn't correct
18 Halted 0 ms 0 KB -