oj.uz

Submission #25766

# Submission time Handle Problem Language Result Execution time Memory
25766 2017-06-24T05:35:22 Z imsifile 별자리 2 (JOI14_constellation2) C++
100 / 100
 786 ms 109060 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;

typedef long long lld;

struct poi {
	lld x, y; int col;
	bool operator< (const poi& c) const {
		if(x != c.x) return x<c.x;
		return y<c.y;
	}
} ba[3030];

struct ps {
	int p1, p2; lld x, y;
	bool operator< (const ps& c) const {
		return y*c.x > c.y*x;
	}
} pairs[4600000];

int N, pcn;
int ord[3030], wid[3030], ccn[3030][3]; lld dap;

int main(){
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%lld%lld%d", &ba[i].x, &ba[i].y, &ba[i].col);
	sort(ba+1, ba+N+1);
	for(int i=1; i<=N; i++){
		for(int j=i+1; j<=N; j++){
			pairs[pcn].p1 = i, pairs[pcn].p2 = j;
			pairs[pcn].y = ba[j].y-ba[i].y;
			pairs[pcn].x = ba[j].x-ba[i].x;
			pcn++;
		}
	}
	sort(pairs, pairs+pcn);

	for(int i=1; i<=N; i++){
		ord[i]=wid[i]=i;
		for(int j=0; j<3; j++) ccn[i][j] = ccn[i-1][j];
		ccn[i][ba[i].col]++;
	}
	for(int i=0; i<pcn; i++){
		int p1=pairs[i].p1, p2=pairs[i].p2;
		int w1=wid[p1], w2=wid[p2];
		if(w1>w2) swap(w1,w2), swap(p1,p2);
		int c1=ba[p1].col, c2=ba[p2].col;

		lld gop1, gop2, im=0;
		gop1 = (lld)ccn[w1-1][(c1+1)%3]*ccn[w1-1][(c1+2)%3];
		gop2 = (lld)(ccn[N][(c2+1)%3]-ccn[w2][(c2+1)%3])*(ccn[N][(c2+2)%3]-ccn[w2][(c2+2)%3]);
		im += gop1*gop2;
		gop1 = (lld)ccn[w1-1][(c2+1)%3]*ccn[w1-1][(c2+2)%3];
		gop2 = (lld)(ccn[N][(c1+1)%3]-ccn[w2][(c1+1)%3])*(ccn[N][(c1+2)%3]-ccn[w2][(c1+2)%3]);
		im += gop1*gop2;
		dap += im;

		ccn[w1][ba[p1].col]--, ccn[w1][ba[p2].col]++;
		swap(ord[w1], ord[w2]), swap(wid[p1], wid[p2]);
	}
	printf("%lld", dap/2);
	return 0;
}

Compilation message

constellation2.cpp: In function 'int main()':
constellation2.cpp:26:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
constellation2.cpp:27:77: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%lld%lld%d", &ba[i].x, &ba[i].y, &ba[i].col);
                                                                             ^

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 109060 KB Output is correct
2 Correct 59 ms 109060 KB Output is correct
3 Correct 79 ms 109060 KB Output is correct
4 Correct 93 ms 109060 KB Output is correct
5 Correct 199 ms 109060 KB Output is correct
6 Correct 353 ms 109060 KB Output is correct
7 Correct 519 ms 109060 KB Output is correct
8 Correct 786 ms 109060 KB Output is correct
9 Correct 739 ms 109060 KB Output is correct
10 Correct 719 ms 109060 KB Output is correct
11 Correct 733 ms 109060 KB Output is correct
12 Correct 766 ms 109060 KB Output is correct
13 Correct 769 ms 109060 KB Output is correct
14 Correct 753 ms 109060 KB Output is correct
15 Correct 779 ms 109060 KB Output is correct
16 Correct 786 ms 109060 KB Output is correct