oj.uz

Submission #658360

# Submission time Handle Problem Language Result Execution time Memory
658360 2022-11-12T22:03:57 Z Richem Circle selection (APIO18_circle_selection) C++14
100 / 100
 2923 ms 471412 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{
    unsigned int 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);
}
 
unordered_map<long long, vector<int>> grille;
bool enleve[MAX_CERCLE] = {0};
 
int quiEnleve[MAX_CERCLE];
 
unsigned int tailleGrille = (1 << 31);
 
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) {
            grille.clear();
            for(int cur = 0; cur < nbCercle; cur++) {
                if(enleve[cur])
                    continue;
                long long xGrille = (long long)cercle[cur].xCentre / tailleGrille;
                int yGrille = cercle[cur].yCentre / tailleGrille;
                
                grille[(xGrille << 32) + yGrille].push_back(cur);
            }
        }
 
        long long xGrille = (long long)cercle[grand].xCentre / tailleGrille, yGrille = (long long)cercle[grand].yCentre / tailleGrille;
 
        vector<int> quiReste;
        for(int deltaX = -2; deltaX <= 2; deltaX++) {
            for(int deltaY = -2; deltaY <= 2; deltaY++) {
                long long nouvX = xGrille + deltaX, nouvY = yGrille + deltaY;
                auto &v = grille[(nouvX << 32) + nouvY];
 
                //for(int type = 0; type < 2; type++) {
 
                    for(int id = v.size()-1; id >= 0; id--) {
                        int autre = v[id];
                        
                        long long xDist = (long long)cercle[grand].xCentre - cercle[autre].xCentre, yDist = (long long)cercle[grand].yCentre - cercle[autre].yCentre;
                        long long rDist = (long long)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;
                            
                            swap(v[id], v[v.size()-1]);
                            v.pop_back();
                        }
                    }
               // }
            }
        }
 
        for(auto nouveau : quiReste) {
            if(enleve[nouveau])
                continue;
            long long xGrille = (long long)cercle[nouveau].xCentre / tailleGrille;
            int yGrille = cercle[nouveau].yCentre / tailleGrille;
            
            grille[(xGrille << 32) + yGrille].push_back(nouveau);
        }
    }
 
    for(int cur = 0; cur < nbCercle; cur++) {
        cout << quiEnleve[cur]+1 << " ";
    }
}
/*
11
9 9 2
13 2 1 11 8 2 3 3 2 3 12 1 12 14 1 9 8 5 2 8 2 5 2 1 14 4 2 14 14 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 336 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 336 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 380 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 5 ms 680 KB Output is correct
20 Correct 4 ms 676 KB Output is correct
21 Correct 5 ms 612 KB Output is correct
22 Correct 17 ms 3968 KB Output is correct
23 Correct 17 ms 4068 KB Output is correct
24 Correct 18 ms 3672 KB Output is correct
25 Correct 16 ms 3824 KB Output is correct
26 Correct 16 ms 4084 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 16112 KB Output is correct
2 Correct 145 ms 15604 KB Output is correct
3 Correct 150 ms 16416 KB Output is correct
4 Correct 129 ms 15528 KB Output is correct
5 Correct 168 ms 16376 KB Output is correct
6 Correct 984 ms 50984 KB Output is correct
7 Correct 196 ms 18140 KB Output is correct
8 Correct 275 ms 25120 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 793 ms 68668 KB Output is correct
3 Correct 2531 ms 180400 KB Output is correct
4 Correct 2526 ms 167988 KB Output is correct
5 Correct 2113 ms 140824 KB Output is correct
6 Correct 725 ms 66456 KB Output is correct
7 Correct 427 ms 56676 KB Output is correct
8 Correct 36 ms 9196 KB Output is correct
9 Correct 2576 ms 160256 KB Output is correct
10 Correct 1566 ms 132464 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2862 ms 471412 KB Output is correct
2 Correct 2923 ms 467356 KB Output is correct
3 Correct 257 ms 16872 KB Output is correct
4 Correct 2850 ms 467152 KB Output is correct
5 Correct 2799 ms 467020 KB Output is correct
6 Correct 156 ms 12700 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 336 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 336 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 380 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 5 ms 680 KB Output is correct
20 Correct 4 ms 676 KB Output is correct
21 Correct 5 ms 612 KB Output is correct
22 Correct 17 ms 3968 KB Output is correct
23 Correct 17 ms 4068 KB Output is correct
24 Correct 18 ms 3672 KB Output is correct
25 Correct 16 ms 3824 KB Output is correct
26 Correct 16 ms 4084 KB Output is correct
27 Correct 6 ms 864 KB Output is correct
28 Correct 5 ms 964 KB Output is correct
29 Correct 5 ms 944 KB Output is correct
30 Correct 43 ms 8332 KB Output is correct
31 Correct 40 ms 8256 KB Output is correct
32 Correct 32 ms 7140 KB Output is correct
33 Correct 46 ms 4832 KB Output is correct
34 Correct 52 ms 5080 KB Output is correct
35 Correct 49 ms 4824 KB Output is correct
36 Correct 805 ms 72564 KB Output is correct
37 Correct 832 ms 65860 KB Output is correct
38 Correct 822 ms 73624 KB Output is correct
39 Correct 257 ms 24216 KB Output is correct
40 Correct 242 ms 24208 KB Output is correct
41 Correct 274 ms 24252 KB Output is correct
42 Correct 82 ms 9992 KB Output is correct
43 Correct 748 ms 132960 KB Output is correct
44 Correct 732 ms 133160 KB Output is correct
45 Correct 780 ms 133036 KB Output is correct
46 Correct 751 ms 133184 KB Output is correct
47 Correct 707 ms 133284 KB Output is correct
48 Correct 699 ms 133244 KB Output is correct
49 Correct 754 ms 133400 KB Output is correct
50 Correct 968 ms 133144 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 336 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 336 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 380 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 5 ms 680 KB Output is correct
20 Correct 4 ms 676 KB Output is correct
21 Correct 5 ms 612 KB Output is correct
22 Correct 17 ms 3968 KB Output is correct
23 Correct 17 ms 4068 KB Output is correct
24 Correct 18 ms 3672 KB Output is correct
25 Correct 16 ms 3824 KB Output is correct
26 Correct 16 ms 4084 KB Output is correct
27 Correct 132 ms 16112 KB Output is correct
28 Correct 145 ms 15604 KB Output is correct
29 Correct 150 ms 16416 KB Output is correct
30 Correct 129 ms 15528 KB Output is correct
31 Correct 168 ms 16376 KB Output is correct
32 Correct 984 ms 50984 KB Output is correct
33 Correct 196 ms 18140 KB Output is correct
34 Correct 275 ms 25120 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 793 ms 68668 KB Output is correct
37 Correct 2531 ms 180400 KB Output is correct
38 Correct 2526 ms 167988 KB Output is correct
39 Correct 2113 ms 140824 KB Output is correct
40 Correct 725 ms 66456 KB Output is correct
41 Correct 427 ms 56676 KB Output is correct
42 Correct 36 ms 9196 KB Output is correct
43 Correct 2576 ms 160256 KB Output is correct
44 Correct 1566 ms 132464 KB Output is correct
45 Correct 2862 ms 471412 KB Output is correct
46 Correct 2923 ms 467356 KB Output is correct
47 Correct 257 ms 16872 KB Output is correct
48 Correct 2850 ms 467152 KB Output is correct
49 Correct 2799 ms 467020 KB Output is correct
50 Correct 156 ms 12700 KB Output is correct
51 Correct 6 ms 864 KB Output is correct
52 Correct 5 ms 964 KB Output is correct
53 Correct 5 ms 944 KB Output is correct
54 Correct 43 ms 8332 KB Output is correct
55 Correct 40 ms 8256 KB Output is correct
56 Correct 32 ms 7140 KB Output is correct
57 Correct 46 ms 4832 KB Output is correct
58 Correct 52 ms 5080 KB Output is correct
59 Correct 49 ms 4824 KB Output is correct
60 Correct 805 ms 72564 KB Output is correct
61 Correct 832 ms 65860 KB Output is correct
62 Correct 822 ms 73624 KB Output is correct
63 Correct 257 ms 24216 KB Output is correct
64 Correct 242 ms 24208 KB Output is correct
65 Correct 274 ms 24252 KB Output is correct
66 Correct 82 ms 9992 KB Output is correct
67 Correct 748 ms 132960 KB Output is correct
68 Correct 732 ms 133160 KB Output is correct
69 Correct 780 ms 133036 KB Output is correct
70 Correct 751 ms 133184 KB Output is correct
71 Correct 707 ms 133284 KB Output is correct
72 Correct 699 ms 133244 KB Output is correct
73 Correct 754 ms 133400 KB Output is correct
74 Correct 968 ms 133144 KB Output is correct
75 Correct 163 ms 10796 KB Output is correct
76 Correct 142 ms 10604 KB Output is correct
77 Correct 153 ms 11836 KB Output is correct
78 Correct 128 ms 11476 KB Output is correct
79 Correct 168 ms 10808 KB Output is correct
80 Correct 139 ms 11332 KB Output is correct
81 Correct 2705 ms 239424 KB Output is correct
82 Correct 2495 ms 236888 KB Output is correct
83 Correct 2536 ms 171108 KB Output is correct
84 Correct 2570 ms 170964 KB Output is correct
85 Correct 2583 ms 226712 KB Output is correct
86 Correct 2550 ms 233536 KB Output is correct
87 Correct 2402 ms 159872 KB Output is correct
88 Correct 889 ms 74848 KB Output is correct
89 Correct 896 ms 75176 KB Output is correct
90 Correct 869 ms 75080 KB Output is correct
91 Correct 885 ms 74944 KB Output is correct
92 Correct 892 ms 74964 KB Output is correct
93 Correct 2653 ms 226568 KB Output is correct
94 Correct 2343 ms 231256 KB Output is correct
95 Correct 2625 ms 226256 KB Output is correct
96 Correct 2378 ms 246544 KB Output is correct
97 Correct 2455 ms 226340 KB Output is correct
98 Correct 1110 ms 49740 KB Output is correct
99 Correct 2466 ms 168676 KB Output is correct
100 Correct 2346 ms 250364 KB Output is correct
101 Correct 1235 ms 66436 KB Output is correct
102 Correct 2234 ms 176732 KB Output is correct
103 Correct 2467 ms 225780 KB Output is correct
104 Correct 2444 ms 228944 KB Output is correct
105 Correct 332 ms 28028 KB Output is correct
106 Correct 2120 ms 304812 KB Output is correct
107 Correct 1665 ms 304984 KB Output is correct
108 Correct 1968 ms 304756 KB Output is correct
109 Correct 1820 ms 304828 KB Output is correct
110 Correct 2000 ms 304324 KB Output is correct
111 Correct 2016 ms 304408 KB Output is correct
112 Correct 1696 ms 304220 KB Output is correct
113 Correct 1704 ms 304260 KB Output is correct
114 Correct 1701 ms 304636 KB Output is correct
115 Correct 2187 ms 304352 KB Output is correct
116 Correct 1673 ms 304324 KB Output is correct