Submission #540413

#	Time	Username	Problem	Language	Result	Execution time	Memory
540413		Killer2501	Circle selection (APIO18_circle_selection)	C++14	100 / 100	1671 ms	34388 KiB

circle_selection

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, int>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 3e5+5;
const int M = 350;
const ll mod = 1e9+7;
const ll inf = 2e15;
int m, t, n, tong, d[N], a[N];
int ans, res[N], b[N];
int lab[N];
ll k;
vector<pii> adj[N];
vector<pll> vi;
bool crowed[N];
ll pw(ll k, ll n)
{
    ll total =1 ;
    for(; n; n >>= 1)
    {
        if(n&1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
struct circle
{
    ll x, y, r, id;
    bool operator < (const circle& c)
    {
    	return (r > c.r) || (r == c.r && id < c.id);
    }
}c[N];
bool check(int i, int j)
{
	return (c[i].x-c[j].x)*(c[i].x-c[j].x)+(c[i].y-c[j].y)*(c[i].y-c[j].y) <= (c[i].r+c[j].r)*(c[i].r+c[j].r);
}
void sol(int icase)
{
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> c[i].x >> c[i].y >> c[i].r;
		c[i].id = i;
		c[i].x += 1e9;
		c[i].y += 1e9;
	}
	sort(c+1, c+1+n);
	int l, r = 0;
	for(int p = 30; p >= 0; p --)
	{
		ll R = (1ll<<p);
		l = r+1;
		r = 0;
		vi.clear();
		for(int i = 1; i <= n; i ++)
		{
			ll x = c[i].x >> p, y = c[i].y >> p;
			if(!r && c[i].r*2 < R)r = i-1;
			vi.pb({(x<<31ll)+y, i});
		}
		if(!r)r = n;
		sort(vi.begin(), vi.end());
        for(int i = l; i <= r; i ++)
		{
			if(res[c[i].id])continue;
			res[c[i].id] = c[i].id;
			for(ll xx = (c[i].x>>p)-2; xx <= (c[i].x>>p)+2; xx ++)
			{
				for(ll yy = (c[i].y>>p)-2; yy <= (c[i].y>>p)+2; yy ++)
				{
					k = (xx<<31ll)+yy;
					int j = lower_bound(vi.begin(), vi.end(), make_pair(k, 0)) - vi.begin();
					while(j < n && vi[j].fi == k)
					{
                        if(!res[c[vi[j].se].id] && check(i, vi[j].se))res[c[vi[j].se].id] = c[i].id;
						++j;
					}
				}
			}

		}
	}
	for(int i = 1; i <= n; i ++)cout << res[i] << " ";
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
    int test = 1;
    //cin >> test;
    for(int i = 1; i <= test; i ++)sol(i);
    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:100:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:101:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13