oj.uz

Submission #540408

# Submission time Handle Problem Language Result Execution time Memory
540408 2022-03-20T10:04:30 Z Killer2501 Circle selection (APIO18_circle_selection) C++14
23 / 100
 3000 ms 33548 KB 
#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) || (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

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7464 KB Output is correct
2 Correct 6 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7388 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Runtime error 11 ms 14692 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 14728 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1489 ms 33020 KB Output is correct
2 Correct 1340 ms 32180 KB Output is correct
3 Correct 1077 ms 33548 KB Output is correct
4 Correct 1378 ms 32532 KB Output is correct
5 Correct 1358 ms 32672 KB Output is correct
6 Correct 1049 ms 33528 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7464 KB Output is correct
2 Correct 6 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7388 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Runtime error 11 ms 14692 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7464 KB Output is correct
2 Correct 6 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7388 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Runtime error 11 ms 14692 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -