oj.uz

Submission #915558

# Submission time Handle Problem Language Result Execution time Memory
915558 2024-01-24T07:14:00 Z prairie2022 별자리 2 (JOI14_constellation2) C++17
100 / 100
 1300 ms 1700 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;

typedef pair<pair<ll, ll>, int> pll;
#define F first.first
#define S first.second
#define C second

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(make_pair(-1ll, 0ll), 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 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 596 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 9 ms 348 KB Output is correct
8 Correct 9 ms 344 KB Output is correct
9 Correct 10 ms 348 KB Output is correct
10 Correct 7 ms 348 KB Output is correct
11 Correct 9 ms 348 KB Output is correct
12 Correct 9 ms 496 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 348 KB Output is correct
2 Correct 97 ms 540 KB Output is correct
3 Correct 111 ms 344 KB Output is correct
4 Correct 111 ms 556 KB Output is correct
5 Correct 282 ms 648 KB Output is correct
6 Correct 527 ms 692 KB Output is correct
7 Correct 897 ms 876 KB Output is correct
8 Correct 1277 ms 1328 KB Output is correct
9 Correct 1271 ms 840 KB Output is correct
10 Correct 1290 ms 1100 KB Output is correct
11 Correct 1266 ms 1092 KB Output is correct
12 Correct 1251 ms 1052 KB Output is correct
13 Correct 1300 ms 1700 KB Output is correct
14 Correct 1278 ms 912 KB Output is correct
15 Correct 1248 ms 848 KB Output is correct
16 Correct 1277 ms 988 KB Output is correct