Submission #811256

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
811256	2023-08-07T03:18:16 Z	CYMario	Circle selection (APIO18_circle_selection)	C++17	Compilation error	0 ms	0 KB

circle_selection

#include <stdio.h>
#include <algorithm>
#include <unordered_map>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
using namespace std;
typedef long long i64;
int rd()
{
    int k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = (k << 1) + (k << 3) + (c ^ 48);
        c = getchar();
    }
    return f == 1 ? k : -k;
}
void wr(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar((x % 10) ^ '0');
}
const int maxn = 300010;
struct point
{
    int x, y;
    point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
    bool operator< (const point& o) const { return (x ^ o.x) ? x < o.x : y < o.y; }
    bool operator==(const point& o) const { return (x == o.x) && (y == o.y); }
};
struct point_hash
{
    size_t operator()(const point &a) const { return hash<int>()(a.x) * 611953 + hash<int>()(a.y) * 7919; }
};
struct circle
{
    point c;
    int r;
} c[maxn];
int n, idx[maxn], ans[maxn];
bool cmp(int a, int b) 
{
    if (c[a].r ^ c[b].r)
        return c[a].r > c[b].r;
    else
        return a < b;
}
unordered_map<point, list<int>, point_hash> mp;
int grid_r;
void build(int r)
{
    grid_r = r;
    mp.clear();
    for (int i = 1; i <= n; ++i)
        if (!ans[i])
            mp[point((c[i].c.x) / grid_r, (c[i].c.y) / grid_r)].push_back(i);
}
bool check(int i, int j)
{
    i64 dis = 1ll * (c[i].c.x - c[j].c.x) * (c[i].c.x - c[j].c.x) + 1ll * (c[i].c.y - c[j].c.y) * (c[i].c.y - c[j].c.y);
    return dis <= 1ll * (c[i].r + c[j].r) * (c[i].r + c[j].r);
}
int main()
{
    n = rd();
    for (int i = 1; i <= n; ++i)
        c[i].c.x = rd(), c[i].c.y = rd(), c[i].r = rd();
    for (int i = 1; i <= n; ++i)
        idx[i] = i;
    sort(idx + 1, idx + n + 1, cmp);
    build(c[idx[1]].r << 1);
    for (int i = 1; i <= n; ++i)
    {
        if (ans[idx[i]])
            continue;
        if ((i64)grid_r > ((i64)(c[idx[i]].r) << 2))
            build(c[idx[i]].r << 1);
        int x = (c[idx[i]].c.x) / grid_r, y = (c[idx[i]].c.y) / grid_r;
        for (int dx = -1; dx <= 1; ++dx)
            for (int dy = -1; dy <= 1; ++dy)
            {
                point pt = point(x + dx, y + dy);
                if (!mp.count(pt))
                    continue;
                list<int>& it = mp[pt];
                for (list<int>::iterator itt = it.begin(); itt != it.end(); )
                {
                    if (check(idx[i], *itt))
                        ans[*itt] = idx[i], it.erase(itt++);
                    else
                        ++itt;
                }
            }
    }
    for (int i = 1; i <= n; ++i)
        wr(ans[i]), putchar(' ');
}

Compilation message

circle_selection.cpp:58:22: error: 'list' was not declared in this scope
   58 | unordered_map<point, list<int>, point_hash> mp;
      |                      ^~~~
circle_selection.cpp:3:1: note: 'std::list' is defined in header '<list>'; did you forget to '#include <list>'?
    2 | #include <algorithm>
  +++ |+#include <list>
    3 | #include <unordered_map>
circle_selection.cpp:58:30: error: template argument 2 is invalid
   58 | unordered_map<point, list<int>, point_hash> mp;
      |                              ^
circle_selection.cpp:58:30: error: template argument 5 is invalid
circle_selection.cpp:58:31: error: expected unqualified-id before ',' token
   58 | unordered_map<point, list<int>, point_hash> mp;
      |                               ^
circle_selection.cpp:58:43: error: expected initializer before '>' token
   58 | unordered_map<point, list<int>, point_hash> mp;
      |                                           ^
circle_selection.cpp: In function 'void build(int)':
circle_selection.cpp:63:5: error: 'mp' was not declared in this scope; did you mean 'cmp'?
   63 |     mp.clear();
      |     ^~
      |     cmp
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:93:22: error: 'mp' was not declared in this scope; did you mean 'cmp'?
   93 |                 if (!mp.count(pt))
      |                      ^~
      |                      cmp
circle_selection.cpp:95:17: error: 'list' was not declared in this scope
   95 |                 list<int>& it = mp[pt];
      |                 ^~~~
circle_selection.cpp:95:17: note: 'std::list' is defined in header '<list>'; did you forget to '#include <list>'?
circle_selection.cpp:95:22: error: expected primary-expression before 'int'
   95 |                 list<int>& it = mp[pt];
      |                      ^~~
circle_selection.cpp:96:27: error: expected primary-expression before 'int'
   96 |                 for (list<int>::iterator itt = it.begin(); itt != it.end(); )
      |                           ^~~
circle_selection.cpp:96:60: error: 'itt' was not declared in this scope; did you mean 'int'?
   96 |                 for (list<int>::iterator itt = it.begin(); itt != it.end(); )
      |                                                            ^~~
      |                                                            int
circle_selection.cpp:96:67: error: 'it' was not declared in this scope; did you mean 'pt'?
   96 |                 for (list<int>::iterator itt = it.begin(); itt != it.end(); )
      |                                                                   ^~
      |                                                                   pt