oj.uz

Submission #259433

# Submission time Handle Problem Language Result Execution time Memory
259433 2020-08-07T19:57:05 Z Namnamseo 별자리 2 (JOI14_constellation2) C++17
100 / 100
 1335 ms 548 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void cppio(){ ios_base::sync_with_stdio(0); cin.tie(0); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define sz(x) (int)(x).size()
#define XY(p) p.x, p.y
const int maxn = 3010;

int n;
pp p[maxn]; int type[maxn];
int js[maxn];

pp operator-(pp a, pp b) {
	return {a.x-b.x, a.y-b.y};
}

int sgn(const pp& v) {
	return (v.x < 0 && v.y == 0) || (v.y < 0);
}

bool ccw(const pp& a, const pp& b) {
	return (b.y*1ll*a.x) > (a.y*1ll*b.x);
}

int call[3], cup[3], cdown[3];

int main()
{
	cppio(); cin >> n;
	rrep(i, n) cin >> p[i].x >> p[i].y >> type[i];
	rrep(i, n) ++call[type[i]];

	ll ans = 0;

	rrep(i, n) {
		for (int j=1, k=0; j<=n; ++j) if (j!=i) js[k++]=j;
		sort(js, js+n-1, [&](const int& j, const int& k) {
			pp vj = p[j]-p[i];
			pp vk = p[k]-p[i];
			int sj = sgn(vj), sk = sgn(vk);
			if (sj != sk) return sj < sk;
			return ccw(vj, vk);
		});

		fill(cup, cup+3, 0);
		fill(cdown, cdown+3, 0);

		int lst = 0;
		auto ok = [&](int j, int k) {
			pp vj = p[js[j]]-p[i];
			pp vk = p[js[k]]-p[i];
			return ccw(vj, vk);
		};
		auto nxt = [](int i) { if (++i == n-1) i = 0; return i; };

		++cup[type[js[0]]];
		for (int j_=0; j_<n-1; ++j_) {
			while (nxt(lst) != j_ && ok(j_, nxt(lst))) {
				lst = nxt(lst);
				++cup[type[js[lst]]];
			}

			int j = js[j_];
			int ti = type[i], tj = type[j];
			--cup[tj];
			rep(k, 3) cdown[k] = call[k] - cup[k];

			--cdown[ti];
			--cdown[tj];

			ans += cup[(ti+1)%3] * 1ll * cup[(ti+2)%3] *
				cdown[(tj+1)%3] * cdown[(tj+2)%3];
			if (lst == j_) {
				lst = nxt(lst);
				++cup[type[js[lst]]];
			}
		}
	}

	ans /= 2;
	cout << ans << endl;
	return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 384 KB Output is correct
2 Correct 111 ms 384 KB Output is correct
3 Correct 127 ms 548 KB Output is correct
4 Correct 138 ms 384 KB Output is correct
5 Correct 312 ms 444 KB Output is correct
6 Correct 564 ms 384 KB Output is correct
7 Correct 951 ms 472 KB Output is correct
8 Correct 1312 ms 504 KB Output is correct
9 Correct 1299 ms 472 KB Output is correct
10 Correct 1254 ms 468 KB Output is correct
11 Correct 1301 ms 468 KB Output is correct
12 Correct 1265 ms 504 KB Output is correct
13 Correct 1335 ms 504 KB Output is correct
14 Correct 1285 ms 504 KB Output is correct
15 Correct 1258 ms 504 KB Output is correct
16 Correct 1304 ms 504 KB Output is correct