oj.uz

Submission #90974

# Submission time Handle Problem Language Result Execution time Memory
90974 2018-12-25T10:51:00 Z tincamatei Circle selection (APIO18_circle_selection) C++14
12 / 100
 3000 ms 50884 KB 
#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 poz[1+MAX_N], rez[1+MAX_N];
double ld[1+MAX_N], rd[1+MAX_N];
 
set<pair<double, int>> sl;
 
bool cmp(int a, int b) {
	return rc[a] > rc[b] || (rc[a] == rc[b] && a < b);
}
 
double dist(int xa, int ya, int xb, int yb) {
	return sqrt((long long)(xa - xb) * (xa - xb) +
	            (long long)(ya - yb) * (ya - yb));
}
 
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, ox, oy, 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]);
	}
	
	srand(time(NULL));

	ox = rand() * rand();
	oy = rand() * rand();
	
	for(int i = 1; i <= n; ++i) {
		xc[i] -= mnx;
		yc[i] -= mny;
 
		double d = dist(ox, oy, xc[i], yc[i]);
 
		ld[i] = d - rc[i];
		rd[i] = d + rc[i];
		
		sl.insert(make_pair(ld[i], i));
		sl.insert(make_pair(rd[i], i));
		poz[i - 1] = i;
	}
 
	sort(poz, poz + n, cmp);
 
	for(int i = 0; i < n; ++i) {
		int x = poz[i];
		
		if(rez[x] == 0) {
			set<pair<double, int> >::iterator it;
 
			it = sl.lower_bound(make_pair(ld[x], -1));
		
			while(it != sl.end() && it->first <= rd[x]) {
				int todel = it->second;
					
				if((long long)(rc[x] + rc[todel]) * (rc[x] + rc[todel]) >= 
				   (long long)(xc[x] - xc[todel]) * (xc[x] - xc[todel]) +
					 (long long)(yc[x] - yc[todel]) * (yc[x] - yc[todel])) {
					rez[todel] = x;
	
					sl.erase(make_pair(ld[todel] + rd[todel] - it->first, todel));
					it = sl.erase(it);
				} else
					it++;
			}
		}
	}
	
	for(int i = 1; i <= n; ++i)
		fprintf(fout, "%d ", rez[i]);
 
#ifdef HOME
	fclose(fin);
	fclose(fout);
#endif
	return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:34: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:37: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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Correct 2 ms 616 KB Output is correct
6 Correct 2 ms 616 KB Output is correct
7 Correct 2 ms 616 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Incorrect 2 ms 716 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1351 ms 50744 KB Output is correct
2 Correct 1356 ms 50884 KB Output is correct
3 Correct 1427 ms 50884 KB Output is correct
4 Correct 1307 ms 50884 KB Output is correct
5 Correct 810 ms 50884 KB Output is correct
6 Correct 849 ms 50884 KB Output is correct
7 Correct 958 ms 50884 KB Output is correct
8 Correct 1099 ms 50884 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 50884 KB Output is correct
2 Correct 545 ms 50884 KB Output is correct
3 Correct 2387 ms 50884 KB Output is correct
4 Correct 2346 ms 50884 KB Output is correct
5 Correct 2283 ms 50884 KB Output is correct
6 Correct 878 ms 50884 KB Output is correct
7 Correct 260 ms 50884 KB Output is correct
8 Correct 30 ms 50884 KB Output is correct
9 Correct 2158 ms 50884 KB Output is correct
10 Execution timed out 3037 ms 50884 KB Time limit exceeded

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1101 ms 50884 KB Output is correct
2 Correct 776 ms 50884 KB Output is correct
3 Execution timed out 3020 ms 50884 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Correct 2 ms 616 KB Output is correct
6 Correct 2 ms 616 KB Output is correct
7 Correct 2 ms 616 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Incorrect 2 ms 716 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Correct 2 ms 616 KB Output is correct
6 Correct 2 ms 616 KB Output is correct
7 Correct 2 ms 616 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Incorrect 2 ms 716 KB Output isn't correct
11 Halted 0 ms 0 KB -