oj.uz

Submission #655733

# Submission time Handle Problem Language Result Execution time Memory
655733 2022-11-05T11:53:44 Z Richem Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 439928 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 9 ms 23764 KB Output is correct
2 Correct 9 ms 23780 KB Output is correct
3 Correct 9 ms 23776 KB Output is correct
4 Correct 9 ms 23764 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 10 ms 23796 KB Output is correct
9 Correct 9 ms 23764 KB Output is correct
10 Correct 9 ms 23764 KB Output is correct
11 Correct 10 ms 23892 KB Output is correct
12 Correct 10 ms 23928 KB Output is correct
13 Correct 10 ms 23920 KB Output is correct
14 Correct 10 ms 23920 KB Output is correct
15 Correct 10 ms 23820 KB Output is correct
16 Correct 11 ms 23940 KB Output is correct
17 Incorrect 11 ms 23792 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 38460 KB Output is correct
2 Incorrect 385 ms 37212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Incorrect 2487 ms 147932 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 3097 ms 439928 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 23780 KB Output is correct
3 Correct 9 ms 23776 KB Output is correct
4 Correct 9 ms 23764 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 10 ms 23796 KB Output is correct
9 Correct 9 ms 23764 KB Output is correct
10 Correct 9 ms 23764 KB Output is correct
11 Correct 10 ms 23892 KB Output is correct
12 Correct 10 ms 23928 KB Output is correct
13 Correct 10 ms 23920 KB Output is correct
14 Correct 10 ms 23920 KB Output is correct
15 Correct 10 ms 23820 KB Output is correct
16 Correct 11 ms 23940 KB Output is correct
17 Incorrect 11 ms 23792 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 23780 KB Output is correct
3 Correct 9 ms 23776 KB Output is correct
4 Correct 9 ms 23764 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 10 ms 23796 KB Output is correct
9 Correct 9 ms 23764 KB Output is correct
10 Correct 9 ms 23764 KB Output is correct
11 Correct 10 ms 23892 KB Output is correct
12 Correct 10 ms 23928 KB Output is correct
13 Correct 10 ms 23920 KB Output is correct
14 Correct 10 ms 23920 KB Output is correct
15 Correct 10 ms 23820 KB Output is correct
16 Correct 11 ms 23940 KB Output is correct
17 Incorrect 11 ms 23792 KB Output isn't correct
18 Halted 0 ms 0 KB -