oj.uz

Submission #658299

# Submission time Handle Problem Language Result Execution time Memory
658299 2022-11-12T19:13:41 Z Richem Circle selection (APIO18_circle_selection) C++14
60 / 100
 3000 ms 96044 KB 
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <time.h>
#pragma once
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

struct uint64_hash {
  static inline uint64_t rotr(uint64_t x, unsigned k) {
    return (x >> k) | (x << (8U * sizeof(uint64_t) - k));
  }
 
  static inline uint64_t hash_int(uint64_t x) noexcept {
    auto h1 = x * (uint64_t)(0xA24BAED4963EE407);
    auto h2 = rotr(x, 32U) * (uint64_t)(0x9FB21C651E98DF25);
    auto h = rotr(h1 + h2, 32U);
    return h;
  }
 
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
    return hash_int(x + FIXED_RANDOM);
  }
};

template <typename K, typename V, typename Hash = uint64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;
template <typename K, typename Hash = uint64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;
template <typename T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

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

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

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

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;

        bool change = 0;
        while(tailleGrille/2 > cercle[grand].rayon) {
            tailleGrille /= 2;
            change = 1;
        }

        if(change) {
            for(int cur = 0; cur < nbCercle; cur++) {
                if(enleve[cur])
                    continue;
                long long xGrille = cercle[cur].xCentre / tailleGrille, yGrille = cercle[cur].yCentre / tailleGrille;
                
                grille[(xGrille << 32) + yGrille].push_back(cur);
            }
        }

        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.erase((nouvX << 32) + nouvY);
                        continue;
                    }

                    for(auto autre : grille[(nouvX << 32) + nouvY]) {
                        long long xDist = cercle[grand].xCentre - cercle[autre].xCentre, yDist = cercle[grand].yCentre - cercle[autre].yCentre;
                        long long rDist = cercle[grand].rayon + cercle[autre].rayon;

                        if(xDist * xDist + yDist * yDist <= rDist * rDist && !enleve[autre]) {
                            enleve[autre] = 1;
                            quiEnleve[cercle[autre].id] = cercle[grand].id;
                        }
                        if(xDist * xDist + yDist * yDist > rDist * rDist) {
                            quiReste.push_back(autre);
                        }
                    }
                }
            }
        }

        for(auto nouveau : quiReste) {
            if(enleve[nouveau])
                continue;
            long long xGrille = cercle[nouveau].xCentre / tailleGrille, yGrille = cercle[nouveau].yCentre / tailleGrille;
            
            grille[(xGrille << 32) + yGrille].push_back(nouveau);
        }
    }

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

Compilation message

circle_selection.cpp:6:9: warning: #pragma once in main file
    6 | #pragma once
      |         ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 1 ms 356 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 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 3 ms 596 KB Output is correct
22 Correct 291 ms 1712 KB Output is correct
23 Correct 45 ms 2960 KB Output is correct
24 Correct 448 ms 1712 KB Output is correct
25 Correct 411 ms 1712 KB Output is correct
26 Correct 484 ms 1712 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 13492 KB Output is correct
2 Correct 144 ms 14944 KB Output is correct
3 Correct 137 ms 13896 KB Output is correct
4 Correct 133 ms 13848 KB Output is correct
5 Correct 178 ms 15812 KB Output is correct
6 Execution timed out 3097 ms 29144 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 677 ms 42968 KB Output is correct
3 Execution timed out 3081 ms 87684 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1727 ms 88748 KB Output is correct
2 Correct 1732 ms 95596 KB Output is correct
3 Correct 304 ms 39300 KB Output is correct
4 Correct 1800 ms 95992 KB Output is correct
5 Correct 1780 ms 96044 KB Output is correct
6 Correct 227 ms 24004 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 1 ms 356 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 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 3 ms 596 KB Output is correct
22 Correct 291 ms 1712 KB Output is correct
23 Correct 45 ms 2960 KB Output is correct
24 Correct 448 ms 1712 KB Output is correct
25 Correct 411 ms 1712 KB Output is correct
26 Correct 484 ms 1712 KB Output is correct
27 Correct 5 ms 780 KB Output is correct
28 Correct 5 ms 724 KB Output is correct
29 Correct 5 ms 852 KB Output is correct
30 Correct 49 ms 5480 KB Output is correct
31 Correct 40 ms 5580 KB Output is correct
32 Correct 1049 ms 3152 KB Output is correct
33 Correct 46 ms 5308 KB Output is correct
34 Correct 50 ms 5240 KB Output is correct
35 Correct 53 ms 4884 KB Output is correct
36 Correct 730 ms 43176 KB Output is correct
37 Correct 636 ms 42884 KB Output is correct
38 Correct 723 ms 43048 KB Output is correct
39 Correct 531 ms 29772 KB Output is correct
40 Correct 528 ms 29688 KB Output is correct
41 Correct 522 ms 30352 KB Output is correct
42 Correct 155 ms 23364 KB Output is correct
43 Correct 789 ms 23444 KB Output is correct
44 Correct 835 ms 23440 KB Output is correct
45 Correct 800 ms 23544 KB Output is correct
46 Correct 728 ms 23448 KB Output is correct
47 Correct 801 ms 23440 KB Output is correct
48 Correct 820 ms 23364 KB Output is correct
49 Correct 834 ms 23448 KB Output is correct
50 Correct 865 ms 23448 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 0 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 1 ms 356 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 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 3 ms 596 KB Output is correct
22 Correct 291 ms 1712 KB Output is correct
23 Correct 45 ms 2960 KB Output is correct
24 Correct 448 ms 1712 KB Output is correct
25 Correct 411 ms 1712 KB Output is correct
26 Correct 484 ms 1712 KB Output is correct
27 Correct 132 ms 13492 KB Output is correct
28 Correct 144 ms 14944 KB Output is correct
29 Correct 137 ms 13896 KB Output is correct
30 Correct 133 ms 13848 KB Output is correct
31 Correct 178 ms 15812 KB Output is correct
32 Execution timed out 3097 ms 29144 KB Time limit exceeded
33 Halted 0 ms 0 KB -