Submission #90998

#	Time	Username	Problem	Language	Result	Execution time	Memory
90998		tincamatei	Circle selection (APIO18_circle_selection)	C++14	100 / 100	2697 ms	381252 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 300000;
int xc[1+MAX_N], yc[1+MAX_N], rc[1+MAX_N];
int rez[1+MAX_N];
int poz[1+MAX_N];
int poz2[1+MAX_N];

bool cmp(int a, int b) {
	return rc[a] > rc[b] || (rc[a] == rc[b] && a < b);
}

bool cmp2(int a, int b) {
	return xc[a] < xc[b] || (xc[a] == xc[b] && yc[a] < yc[b]);
}

bool cmp3(int a, int b) {
	return yc[a] < yc[b];
}

double dist(int a, int b) {
	return sqrt((long long)(xc[a] - xc[b]) * (xc[a] - xc[b]) +
	            (long long)(yc[a] - yc[b]) * (yc[a] - yc[b]));
}

vector<pair<int, vector<int> > > grid, aux;

void init(int n, int d) {
	sort(poz2, poz2 + n, cmp2);

	int lastx = -1;
	for(int i = 0; i < n; ++i) {
		int p = poz2[i];
		
		if(xc[p] / d == lastx)
			grid.back().second.push_back(p);
		else {
			lastx = xc[p] / d;
			grid.push_back(make_pair(lastx, vector<int>(1, p)));
		}
	}
	
	for(int i = 0; i < grid.size(); ++i)
		sort(grid[i].second.begin(), grid[i].second.end(), cmp3);
}

void rescale(int n, int d) {
	for(auto it: grid) {
		vector<int> st, dr;
		for(auto it2: it.second) {
			if(xc[it2] / d == it.first * 2)
				st.push_back(it2);
			else
				dr.push_back(it2);
		}

		if(st.size() > 0)
			aux.push_back(make_pair(it.first * 2, st));
		if(dr.size() > 0)
			aux.push_back(make_pair(it.first * 2 + 1, dr));
	}
	grid.clear();
	grid = aux;
	aux.clear();
}

int getStrip(int x) {
	int st = 0, dr = grid.size();
	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		if(grid[mid].first <= x)
			st = mid;
		else
			dr = mid;
	}

	return st;
}

int getFirstE(int strip, int y) {
	int st = -1, dr = grid[strip].second.size();
	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		if(yc[grid[strip].second[mid]] < y)
			st = mid;
		else
			dr = mid;
	}
	return dr;
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int n;
	int mnx, mny;

	mnx = mny = 1000000000;
	
	fscanf(fin, "%d", &n);
	for(int i = 1; i <= n; ++i) {
		fscanf(fin, "%d%d%d", &xc[i], &yc[i], &rc[i]);
		mnx = min(mnx, xc[i]);
		mny = min(mny, yc[i]);
		poz[i - 1] = poz2[i - 1] = i;
	}

	for(int i = 1; i <= n; ++i) {
		xc[i] -= mnx;
		yc[i] -= mny;
	}

	sort(poz, poz + n, cmp);

	int lastr = (1 << 30);
	init(n, lastr);

	for(int i = 0; i < n; ++i) {
		int p = poz[i];

		while(rc[p] * 2 <= lastr) {
			lastr /= 2;
			rescale(n, lastr);
		}
		
		if(rez[p] == 0) {
			int x2 = xc[p] / lastr, y2 = yc[p] / lastr;
			for(int strip = x2 - 2; strip <= x2 + 2; ++strip) {
				int pstrip = getStrip(strip);
				if(grid[pstrip].first == strip) {
					int j = getFirstE(pstrip, (y2 - 2) * lastr);
					while(j < grid[pstrip].second.size() &&
					      yc[grid[pstrip].second[j]] < (long long)(y2 + 3) * lastr) {
						int p2 = grid[pstrip].second[j];
						
						if(rez[p2] == 0 && dist(p, p2) <= rc[p] + rc[p2])
							rez[p2] = p;

						++j;
					}
				}
			}
		}
	}

	for(int i = 1; i <= n; ++i)
		fprintf(fout, "%d ", rez[i]);

#ifdef HOME
	fclose(fin);
	fclose(fout);
#endif
	return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'void init(int, int)':
circle_selection.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grid.size(); ++i)
                 ~~^~~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:140:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while(j < grid[pstrip].second.size() &&
            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:108:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d", &n);
  ~~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:110:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d%d", &xc[i], &yc[i], &rc[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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