oj.uz

Submission #25751

# Submission time Handle Problem Language Result Execution time Memory
25751 2017-06-24T04:33:22 Z kriii 별자리 2 (JOI14_constellation2) C++14
100 / 100
 1433 ms 1512 KB 
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

int N,X[3030],Y[3030],C[3030];

struct pt{
	pt(){}
	pt(int x_, int y_, int c_){
		x = x_; y = y_; c = c_;
		d = atan2(y,x);
	}
	int x,y,c; double d;

	bool operator <(const pt &t)const{
		return d < t.d;
	}
}P[6060];

double pi = acos(-1.0);

int main()
{
	scanf ("%d",&N);
	for (int i=0;i<N;i++) scanf ("%d %d %d",&X[i],&Y[i],&C[i]);

	long long ans = 0;
	for (int v=0;v<N;v++){
		int c = 0;
		for (int j=0;j<N;j++) if (j != v) P[c++] = pt(X[j]-X[v],Y[j]-Y[v],C[j]);
		sort(P,P+c);

		int A[3] = {0,};
		for (int i=0;i<c;i++){
			A[P[i].c]++;
			P[i+c] = P[i];
			P[i+c].d += 2 * pi;
		}

		int B[3] = {0,};
		for (int i=0,j=0;i<c;i++){
			while (P[i].d + pi > P[j].d) B[P[j++].c]++;
			long long res = 1;
			for (int k=0;k<3;k++) if (k != C[v]) res *= (A[k] - B[k]);
			B[P[i].c]--;
			for (int k=0;k<3;k++) if (k != P[i].c) res *= B[k];
			ans += res;
		}
	}
	printf ("%lld\n",ans/2);

	return 0;
}

Compilation message

constellation2.cpp: In function 'int main()':
constellation2.cpp:25:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&N);
                 ^
constellation2.cpp:26:60: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0;i<N;i++) scanf ("%d %d %d",&X[i],&Y[i],&C[i]);
                                                            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1512 KB Output is correct
2 Correct 0 ms 1512 KB Output is correct
3 Correct 0 ms 1512 KB Output is correct
4 Correct 0 ms 1512 KB Output is correct
5 Correct 0 ms 1512 KB Output is correct
6 Correct 0 ms 1512 KB Output is correct
7 Correct 0 ms 1512 KB Output is correct
8 Correct 0 ms 1512 KB Output is correct
9 Correct 0 ms 1512 KB Output is correct
10 Correct 0 ms 1512 KB Output is correct
11 Correct 0 ms 1512 KB Output is correct
12 Correct 0 ms 1512 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1512 KB Output is correct
2 Correct 0 ms 1512 KB Output is correct
3 Correct 0 ms 1512 KB Output is correct
4 Correct 3 ms 1512 KB Output is correct
5 Correct 6 ms 1512 KB Output is correct
6 Correct 16 ms 1512 KB Output is correct
7 Correct 9 ms 1512 KB Output is correct
8 Correct 13 ms 1512 KB Output is correct
9 Correct 9 ms 1512 KB Output is correct
10 Correct 6 ms 1512 KB Output is correct
11 Correct 13 ms 1512 KB Output is correct
12 Correct 9 ms 1512 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 1512 KB Output is correct
2 Correct 123 ms 1512 KB Output is correct
3 Correct 146 ms 1512 KB Output is correct
4 Correct 149 ms 1512 KB Output is correct
5 Correct 353 ms 1512 KB Output is correct
6 Correct 596 ms 1512 KB Output is correct
7 Correct 916 ms 1512 KB Output is correct
8 Correct 1403 ms 1512 KB Output is correct
9 Correct 1433 ms 1512 KB Output is correct
10 Correct 1166 ms 1512 KB Output is correct
11 Correct 1299 ms 1512 KB Output is correct
12 Correct 1269 ms 1512 KB Output is correct
13 Correct 1309 ms 1512 KB Output is correct
14 Correct 1386 ms 1512 KB Output is correct
15 Correct 1363 ms 1512 KB Output is correct
16 Correct 1386 ms 1512 KB Output is correct