oj.uz

Submission #915556

# Submission time Handle Problem Language Result Execution time Memory
915556 2024-01-24T07:09:38 Z prairie2022 별자리 2 (JOI14_constellation2) C++17
100 / 100
 1182 ms 1416 KB 
#include<bits/stdc++.h>
using namespace std;

#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
typedef long long ll;

struct pll{
	ll F, S;
	int C;
	pll(){}
	pll(ll F, ll S, int C) : F(F), S(S), C(C){}
};

inline pll operator-(pll p1, pll p2){
	return {p1.F-p2.F, p1.S-p2.S, p1.C};
}

inline ll dot(pll p1, pll p2){
	return p1.F*p2.F+p1.S*p2.S;
}

inline ll cross(pll p1, pll p2){
	return p1.F*p2.S-p1.S*p2.F;
}

inline int sign(ll n){
	return n?(n>0?1:-1):0;
}

inline bool is_neg(pll p){
	return p.S<0 || (!p.S && p.F<0);
}

inline bool cmp(pll p1, pll p2){
	bool b1 = is_neg(p1), b2 = is_neg(p2);
	if(b1!=b2) return b1<b2;
	ll area = cross(p1, p2);
	return area?area>0:(abs(p1.F)<abs(p2.F) || abs(p1.S)<abs(p2.S));
}

int main(){
	fastio
	int n;
	ll ans = 0;
	cin >> n;
	vector<pll> p(n);
	for(int i=0; i<n; i++) cin >> p[i].F >> p[i].S >> p[i].C;
	n--;
	for(int i=0; i<=n; i++){
		vector<pll> q;
		for(int j=0; j<=n; j++)
			if(j!=i) q.push_back(p[j]-p[i]);
		sort(q.begin(), q.end(), cmp);
		int cnt0[3], cnt1[3]; // cnt0 with origin, cnt1 with polar angle
		memset(cnt0, 0, sizeof(cnt0)), memset(cnt1, 0, sizeof(cnt1));
		for(const pll &qq: q){
			if(is_neg(qq)) cnt1[qq.C]++;
			else cnt0[qq.C]++;
		}
		int k = lower_bound(q.begin(), q.end(), pll(-1, 0, 0), cmp)-q.begin();
		q.resize(n<<1);
		copy(q.begin(), q.begin()+n, q.begin()+n);
		for(int j=0; j<n; j++){
			cnt1[q[j].C]++, cnt0[q[j].C]--;
			while(j==k || cross(q[j], q[k])>0){
				cnt0[q[k].C]++, cnt1[q[k].C]--, k++;
			}
			ans += 1ll*cnt0[(p[i].C+1)%3]*cnt0[(p[i].C+2)%3]*cnt1[(q[j].C+1)%3]*cnt1[(q[j].C+2)%3];
		}
	}
	cout << (ans>>1) << '\n';
	return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 348 KB Output is correct
2 Correct 89 ms 560 KB Output is correct
3 Correct 101 ms 344 KB Output is correct
4 Correct 101 ms 348 KB Output is correct
5 Correct 276 ms 912 KB Output is correct
6 Correct 475 ms 712 KB Output is correct
7 Correct 811 ms 1088 KB Output is correct
8 Correct 1167 ms 1296 KB Output is correct
9 Correct 1160 ms 1416 KB Output is correct
10 Correct 1150 ms 1156 KB Output is correct
11 Correct 1163 ms 1208 KB Output is correct
12 Correct 1146 ms 928 KB Output is correct
13 Correct 1182 ms 904 KB Output is correct
14 Correct 1150 ms 1176 KB Output is correct
15 Correct 1163 ms 1020 KB Output is correct
16 Correct 1171 ms 892 KB Output is correct