oj.uz

Submission #110188

# Submission time Handle Problem Language Result Execution time Memory
110188 2019-05-10T03:39:04 Z baluteshih Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 40372 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cerr << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll ans[300005],x[300005],y[300005],r[300005],arr[300005],arr2[300005],rmax,n;
vector<vector<vector<ll>>> v;
vector<vector<ll>> sigy;
vector<ll> sigx;

bool yee(ll a,ll b)
{
	if(x[a]==x[b]) return y[a]<y[b];
	return x[a]<x[b];
}

bool yee2(ll a,ll b)
{
	if(r[a]==r[b]) return a<b;
	return r[a]>r[b];
}

bool intersect(ll a,ll b)
{
	return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])<=(r[a]+r[b])*(r[a]+r[b]);
}

ll blk(ll x)
{
	if(x>0) return x/rmax;
	return x/rmax-1;
}

void rebuild()
{
	vector<vector<vector<ll>>>().swap(v);
	vector<ll>().swap(sigx),vector<vector<ll>>().swap(sigy);
	for(int i=1;i<=n;++i)
		if(!ans[arr[i]])
			if(v.empty()||sigx.back()!=blk(x[arr[i]]))
				v.pb(vector<vector<ll>>(1,vector<ll>(1,arr[i]))),sigx.pb(blk(x[arr[i]])),sigy.pb(vector<ll>(1,blk(y[arr[i]])));
			else
				if(sigy.back().back()==blk(y[arr[i]])) v.back().back().pb(arr[i]);
				else v.back().pb(vector<ll>(1,arr[i])),sigy.back().pb(blk(y[arr[i]]));
}

int main()
{jizz
	cin >> n;
	for(int i=1;i<=n;++i)
		cin >> x[i] >> y[i] >> r[i],arr2[i]=arr[i]=i,rmax=max(rmax,r[i]);
	sort(arr+1,arr+n+1,yee),sort(arr2+1,arr2+n+1,yee2),rebuild();
	for(int i=1;i<=n;++i)
	{
		int cur=arr2[i];
		if(ans[cur]) continue;
		if(r[cur]*2<=rmax)
			rmax=r[cur],rebuild();
		for(int j=0;j<v.size();++j)
		{
			for(int k=0;k<v[j].size();++k)
			{
				vector<ll> tmp;
				for(auto p:v[j][k])
					if(intersect(p,cur)) ans[p]=cur;
					else tmp.pb(p);
				v[j][k].swap(tmp);
			}
		}
	}
	for(int i=1;i<=n;++i)
		cout << ans[i] << " \n"[i==n],assert(ans[i]!=0);
}

Compilation message

circle_selection.cpp: In function 'void rebuild()':
circle_selection.cpp:50:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   if(!ans[arr[i]])
     ^
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v.size();++j)
               ~^~~~~~~~~
circle_selection.cpp:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<v[j].size();++k)
                ~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 6 ms 896 KB Output is correct
20 Correct 7 ms 896 KB Output is correct
21 Correct 6 ms 924 KB Output is correct
22 Correct 830 ms 1368 KB Output is correct
23 Correct 736 ms 1244 KB Output is correct
24 Correct 849 ms 1356 KB Output is correct
25 Correct 820 ms 1656 KB Output is correct
26 Correct 962 ms 1416 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 18548 KB Output is correct
2 Correct 342 ms 17512 KB Output is correct
3 Correct 319 ms 17644 KB Output is correct
4 Correct 338 ms 16872 KB Output is correct
5 Execution timed out 3046 ms 18704 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Execution timed out 3009 ms 15884 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 6 ms 896 KB Output is correct
20 Correct 7 ms 896 KB Output is correct
21 Correct 6 ms 924 KB Output is correct
22 Correct 830 ms 1368 KB Output is correct
23 Correct 736 ms 1244 KB Output is correct
24 Correct 849 ms 1356 KB Output is correct
25 Correct 820 ms 1656 KB Output is correct
26 Correct 962 ms 1416 KB Output is correct
27 Correct 14 ms 1536 KB Output is correct
28 Correct 11 ms 1280 KB Output is correct
29 Correct 11 ms 1408 KB Output is correct
30 Execution timed out 3037 ms 1920 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 6 ms 896 KB Output is correct
20 Correct 7 ms 896 KB Output is correct
21 Correct 6 ms 924 KB Output is correct
22 Correct 830 ms 1368 KB Output is correct
23 Correct 736 ms 1244 KB Output is correct
24 Correct 849 ms 1356 KB Output is correct
25 Correct 820 ms 1656 KB Output is correct
26 Correct 962 ms 1416 KB Output is correct
27 Correct 330 ms 18548 KB Output is correct
28 Correct 342 ms 17512 KB Output is correct
29 Correct 319 ms 17644 KB Output is correct
30 Correct 338 ms 16872 KB Output is correct
31 Execution timed out 3046 ms 18704 KB Time limit exceeded
32 Halted 0 ms 0 KB -