답안 #90981 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90981	2018-12-25T11:39:21 Z	tincamatei	원 고르기 (APIO18_circle_selection)	C++14	12 / 100	3000 ms	438384 KB

circle_selection

#include <bits/stdc++.h>

using namespace std;

map<int, map<int, vector<int> > > grid;

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];

void rescale(int n, int d) {
	grid.clear();
	for(int i = 1; i <= n; ++i)
		if(rez[i] == 0)
			grid[xc[i] / d][yc[i] / d].push_back(i);
}

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

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] = i;
	}

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

	sort(poz, poz + n, cmp);

	int lastr = (1 << 29);
	rescale(n, lastr);

	for(int i = 0; i < n; ++i) {
		int p = poz[i];
		if(rez[p] == 0) {
			while(rc[p] * 2 <= lastr) {
				lastr = rc[p];
				rescale(n, lastr);
			}

			int x = xc[p] / lastr, y = yc[p] / lastr;

			for(int i = x - 2; i <= x + 2; ++i)
				for(int j = y - 2; j <= y + 2; ++j) {
					for(auto it: grid[i][j])
						if(rez[it] == 0 && dist(p, it) <= rc[p] + rc[it])
							rez[it] = p;
				}
		}
	}

	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:42: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:44: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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	408 KB	Output is correct
3	Correct	2 ms	616 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	616 KB	Output is correct
9	Correct	2 ms	616 KB	Output is correct
10	Correct	2 ms	616 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	2 ms	756 KB	Output is correct
13	Correct	2 ms	800 KB	Output is correct
14	Correct	2 ms	800 KB	Output is correct
15	Correct	2 ms	800 KB	Output is correct
16	Correct	2 ms	800 KB	Output is correct
17	Correct	2 ms	800 KB	Output is correct
18	Correct	2 ms	800 KB	Output is correct
19	Correct	5 ms	800 KB	Output is correct
20	Correct	5 ms	800 KB	Output is correct
21	Incorrect	5 ms	800 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	195 ms	8916 KB	Output is correct
2	Correct	208 ms	8916 KB	Output is correct
3	Correct	204 ms	10184 KB	Output is correct
4	Correct	198 ms	10184 KB	Output is correct
5	Correct	266 ms	13640 KB	Output is correct
6	Correct	1890 ms	99412 KB	Output is correct
7	Correct	378 ms	99412 KB	Output is correct
8	Correct	742 ms	99412 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	99412 KB	Output is correct
2	Correct	1759 ms	107044 KB	Output is correct
3	Execution timed out	3121 ms	320760 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3073 ms	438384 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	408 KB	Output is correct
3	Correct	2 ms	616 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	616 KB	Output is correct
9	Correct	2 ms	616 KB	Output is correct
10	Correct	2 ms	616 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	2 ms	756 KB	Output is correct
13	Correct	2 ms	800 KB	Output is correct
14	Correct	2 ms	800 KB	Output is correct
15	Correct	2 ms	800 KB	Output is correct
16	Correct	2 ms	800 KB	Output is correct
17	Correct	2 ms	800 KB	Output is correct
18	Correct	2 ms	800 KB	Output is correct
19	Correct	5 ms	800 KB	Output is correct
20	Correct	5 ms	800 KB	Output is correct
21	Incorrect	5 ms	800 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	408 KB	Output is correct
3	Correct	2 ms	616 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	616 KB	Output is correct
9	Correct	2 ms	616 KB	Output is correct
10	Correct	2 ms	616 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	2 ms	756 KB	Output is correct
13	Correct	2 ms	800 KB	Output is correct
14	Correct	2 ms	800 KB	Output is correct
15	Correct	2 ms	800 KB	Output is correct
16	Correct	2 ms	800 KB	Output is correct
17	Correct	2 ms	800 KB	Output is correct
18	Correct	2 ms	800 KB	Output is correct
19	Correct	5 ms	800 KB	Output is correct
20	Correct	5 ms	800 KB	Output is correct
21	Incorrect	5 ms	800 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

답안 #90981

Compilation message

Subtask #1 0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0