oj.uz

Submission #658288

# Submission time Handle Problem Language Result Execution time Memory
658288 2022-11-12T19:01:15 Z Richem Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 681256 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;
    }

    bool intersecte(Cercle autre) {
        long long xDist = xCentre - autre.xCentre, yDist = yCentre - autre.yCentre;
        long long rDist = rayon + autre.rayon;

        return xDist * xDist + yDist * yDist <= rDist * rDist;
    }
};

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

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

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;

        while(tailleGrille/2 > cercle[grand].rayon) {
            tailleGrille /= 2;
            calcGrille(tailleGrille);
        }

        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]) {
                        if(cercle[grand].intersecte(cercle[autre]) && !enleve[autre]) {
                            enleve[autre] = 1;
                            quiEnleve[cercle[autre].id] = cercle[grand].id;
                        }
                        if(!cercle[grand].intersecte(cercle[autre])) {
                            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 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 0 ms 340 KB Output is correct
6 Correct 1 ms 340 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 0 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 472 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 5 ms 1112 KB Output is correct
20 Correct 4 ms 1112 KB Output is correct
21 Correct 5 ms 1144 KB Output is correct
22 Correct 34 ms 11052 KB Output is correct
23 Correct 33 ms 11116 KB Output is correct
24 Correct 34 ms 11040 KB Output is correct
25 Correct 45 ms 10936 KB Output is correct
26 Correct 36 ms 10992 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 45516 KB Output is correct
2 Correct 332 ms 56096 KB Output is correct
3 Correct 265 ms 55140 KB Output is correct
4 Correct 260 ms 44196 KB Output is correct
5 Correct 553 ms 105328 KB Output is correct
6 Correct 1970 ms 128944 KB Output is correct
7 Correct 607 ms 95556 KB Output is correct
8 Correct 760 ms 112252 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1029 ms 98848 KB Output is correct
3 Execution timed out 3065 ms 368584 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 340 KB Output is correct
6 Correct 1 ms 340 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 0 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 472 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 5 ms 1112 KB Output is correct
20 Correct 4 ms 1112 KB Output is correct
21 Correct 5 ms 1144 KB Output is correct
22 Correct 34 ms 11052 KB Output is correct
23 Correct 33 ms 11116 KB Output is correct
24 Correct 34 ms 11040 KB Output is correct
25 Correct 45 ms 10936 KB Output is correct
26 Correct 36 ms 10992 KB Output is correct
27 Correct 10 ms 1812 KB Output is correct
28 Correct 8 ms 1680 KB Output is correct
29 Correct 8 ms 1556 KB Output is correct
30 Correct 92 ms 21520 KB Output is correct
31 Correct 96 ms 21496 KB Output is correct
32 Correct 77 ms 21356 KB Output is correct
33 Correct 77 ms 12312 KB Output is correct
34 Correct 77 ms 12156 KB Output is correct
35 Correct 114 ms 14252 KB Output is correct
36 Correct 1101 ms 174456 KB Output is correct
37 Correct 1164 ms 173828 KB Output is correct
38 Correct 1010 ms 174344 KB Output is correct
39 Correct 897 ms 43856 KB Output is correct
40 Correct 876 ms 44840 KB Output is correct
41 Correct 839 ms 49160 KB Output is correct
42 Correct 321 ms 47128 KB Output is correct
43 Correct 886 ms 98176 KB Output is correct
44 Correct 869 ms 98144 KB Output is correct
45 Correct 912 ms 98176 KB Output is correct
46 Correct 854 ms 98148 KB Output is correct
47 Correct 775 ms 98240 KB Output is correct
48 Correct 851 ms 98216 KB Output is correct
49 Correct 865 ms 98232 KB Output is correct
50 Correct 848 ms 98156 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 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 0 ms 340 KB Output is correct
6 Correct 1 ms 340 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 0 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 472 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 5 ms 1112 KB Output is correct
20 Correct 4 ms 1112 KB Output is correct
21 Correct 5 ms 1144 KB Output is correct
22 Correct 34 ms 11052 KB Output is correct
23 Correct 33 ms 11116 KB Output is correct
24 Correct 34 ms 11040 KB Output is correct
25 Correct 45 ms 10936 KB Output is correct
26 Correct 36 ms 10992 KB Output is correct
27 Correct 269 ms 45516 KB Output is correct
28 Correct 332 ms 56096 KB Output is correct
29 Correct 265 ms 55140 KB Output is correct
30 Correct 260 ms 44196 KB Output is correct
31 Correct 553 ms 105328 KB Output is correct
32 Correct 1970 ms 128944 KB Output is correct
33 Correct 607 ms 95556 KB Output is correct
34 Correct 760 ms 112252 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1029 ms 98848 KB Output is correct
37 Execution timed out 3065 ms 368584 KB Time limit exceeded
38 Halted 0 ms 0 KB -