Submission #25766

#	Time	Username	Problem	Language	Result	Execution time	Memory
25766		imsifile	별자리 2 (JOI14_constellation2)	C++98	100 / 100	786 ms	109060 KiB

constellation2

#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 (stderr)

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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45