oj.uz

답안 #772073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
772073 2023-07-03T15:16:40 Z davitmarg 원 고르기 (APIO18_circle_selection) C++17
72 / 100
 3000 ms 51676 KB 
/*
DavitMarg
In pr honky-tonk,
Down in Mexico
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair    
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 500005;

#define circle pair<pair<LL, LL>, pair<LL, int>>
#define X first.first
#define Y first.second
#define R second.first
#define I second.second

int n;
circle p[N];
LL rad;
map<pair<LL, LL>, vector<circle>> g;
int ans[N];

bool intersect(circle a, circle b)
{
    LL dx = a.X - b.X;
    LL dy = a.Y - b.Y;
    return (dx * dx) + (dy * dy) <= (a.R + b.R) * (a.R + b.R);
}

void changeScale()
{
   g.clear();
   for (int i = 1; i <= n; i++)
       g[MP(p[i].X / rad, p[i].Y / rad)].push_back(p[i]);
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].X >> p[i].Y >> p[i].R;
        p[i].X += mod;
        p[i].Y += mod;
        p[i].I = i;
        rad = max(rad, p[i].R);
    }

    


    int cur = 0;

    sort(p + 1, p + 1 + n, [](circle a, circle b) {
        if(a.R != b.R)
            return a.R > b.R;
        return a.I < b.I;
    });

    changeScale();

    for (int i = 1; i <= n; i++)
    {
        if (ans[p[i].I])
            continue;

        if (p[i].R * 2 < rad)
        {
            while (p[i].R * 2 < rad)
                rad /= 2;
            changeScale();
        }

        LL x = p[i].X / rad;
        LL y = p[i].Y / rad;

        for(int kx = x - 2; kx <= x + 2; kx++)
            for (int ky = y - 2; ky <= y + 2; ky++)
            {
                if (g.find(MP(kx, ky)) == g.end())
                    continue;
                vector<circle>& c = g[MP(kx, ky)];
                for (int j = 0; j < c.size(); j++)
                {
                    if (ans[c[j].I])
                        continue;
                    if(intersect(p[i], c[j]))
                        ans[c[j].I] = p[i].I;
                }
            }
    }

    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;

}

int main()
{
    fastIO;
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

/*

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: In function 'void solve()':
circle_selection.cpp:107:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |                 for (int j = 0; j < c.size(); j++)
      |                                 ~~^~~~~~~~~~
circle_selection.cpp:76:9: warning: unused variable 'cur' [-Wunused-variable]
   76 |     int cur = 0;
      |         ^~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 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 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 2 ms 1000 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 5 ms 1012 KB Output is correct
22 Correct 21 ms 1264 KB Output is correct
23 Correct 22 ms 1236 KB Output is correct
24 Correct 22 ms 1268 KB Output is correct
25 Correct 19 ms 1236 KB Output is correct
26 Correct 20 ms 1280 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 25716 KB Output is correct
2 Correct 137 ms 26508 KB Output is correct
3 Correct 125 ms 22792 KB Output is correct
4 Correct 127 ms 27208 KB Output is correct
5 Correct 700 ms 41940 KB Output is correct
6 Correct 2191 ms 51272 KB Output is correct
7 Correct 1323 ms 48964 KB Output is correct
8 Correct 1869 ms 51676 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1463 ms 16872 KB Output is correct
3 Execution timed out 3067 ms 48452 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1350 ms 50348 KB Output is correct
2 Correct 982 ms 50712 KB Output is correct
3 Correct 354 ms 33608 KB Output is correct
4 Correct 1155 ms 50724 KB Output is correct
5 Correct 1131 ms 50664 KB Output is correct
6 Correct 232 ms 30244 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 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 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 2 ms 1000 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 5 ms 1012 KB Output is correct
22 Correct 21 ms 1264 KB Output is correct
23 Correct 22 ms 1236 KB Output is correct
24 Correct 22 ms 1268 KB Output is correct
25 Correct 19 ms 1236 KB Output is correct
26 Correct 20 ms 1280 KB Output is correct
27 Correct 13 ms 1936 KB Output is correct
28 Correct 5 ms 1216 KB Output is correct
29 Correct 7 ms 1236 KB Output is correct
30 Correct 51 ms 1924 KB Output is correct
31 Correct 47 ms 1940 KB Output is correct
32 Correct 48 ms 1940 KB Output is correct
33 Correct 42 ms 7712 KB Output is correct
34 Correct 39 ms 8436 KB Output is correct
35 Correct 396 ms 17236 KB Output is correct
36 Correct 1324 ms 16888 KB Output is correct
37 Correct 1102 ms 16896 KB Output is correct
38 Correct 1141 ms 16880 KB Output is correct
39 Correct 306 ms 13232 KB Output is correct
40 Correct 284 ms 13196 KB Output is correct
41 Correct 311 ms 13156 KB Output is correct
42 Correct 200 ms 16844 KB Output is correct
43 Correct 215 ms 16708 KB Output is correct
44 Correct 228 ms 16640 KB Output is correct
45 Correct 213 ms 16740 KB Output is correct
46 Correct 235 ms 16728 KB Output is correct
47 Correct 240 ms 16676 KB Output is correct
48 Correct 213 ms 16668 KB Output is correct
49 Correct 218 ms 16716 KB Output is correct
50 Correct 235 ms 16672 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 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 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 2 ms 1000 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 5 ms 1012 KB Output is correct
22 Correct 21 ms 1264 KB Output is correct
23 Correct 22 ms 1236 KB Output is correct
24 Correct 22 ms 1268 KB Output is correct
25 Correct 19 ms 1236 KB Output is correct
26 Correct 20 ms 1280 KB Output is correct
27 Correct 158 ms 25716 KB Output is correct
28 Correct 137 ms 26508 KB Output is correct
29 Correct 125 ms 22792 KB Output is correct
30 Correct 127 ms 27208 KB Output is correct
31 Correct 700 ms 41940 KB Output is correct
32 Correct 2191 ms 51272 KB Output is correct
33 Correct 1323 ms 48964 KB Output is correct
34 Correct 1869 ms 51676 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 1463 ms 16872 KB Output is correct
37 Execution timed out 3067 ms 48452 KB Time limit exceeded
38 Halted 0 ms 0 KB -