oj.uz

Submission #261776

# Submission time Handle Problem Language Result Execution time Memory
261776 2020-08-12T04:51:10 Z onjo0127 None (JOI12_constellation) C++11
100 / 100
 77 ms 5360 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(V) ((int)(V).size())
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MOD = 1e9 + 7;

struct star {
	int X, Y, ty;
} A[100009];

int CCW(star A, star B, star C) {
	ll tmp = 1LL*A.X*B.Y + 1LL*B.X*C.Y + 1LL*C.X*A.Y - 1LL*A.Y*B.X - 1LL*B.Y*C.X - 1LL*C.Y*A.X;
	if(tmp < 0) return -1;
	if(tmp == 0) return 0;
	if(tmp > 0) return +1;
}

long long get(int x) {
	long long ans = 1;
	for(int i=0; i<x; i++) ans *= 2, ans %= MOD;
	return ans;
}

int main() {
	int ct[3] = {0, 0, 0};
	int N; long long tot = 0;
	scanf("%d", &N);
	for(int i=1; i<=N; i++) {
		scanf("%d%d%d", &A[i].X, &A[i].Y, &A[i].ty);
		if(A[i].ty == 0) ++tot;
		++ct[A[i].ty];
	}
	sort(A+1, A+N+1, [&](star PP, star QQ) {
		if(PP.X == QQ.X) return PP.Y < QQ.Y;
		return PP.X < QQ.X;
	});
	vector<star> H;
	sort(A+2, A+N+1, [&](star PP, star QQ) { return CCW(A[1], PP, QQ) > 0; });
	H.push_back(A[1]); H.push_back(A[2]);
	for(int i=3; i<=N; i++) {
		while(sz(H) >= 2 && CCW(H[sz(H) - 2], H[sz(H) - 1], A[i]) < 0) H.pop_back();
		H.push_back(A[i]);
	}
	long long hto = 0;
	for(auto& it: H) if(it.ty == 0) ++hto;
	int p = -1, ch = 0, c = -1; long long cnt = 0, ans = 0;
	for(int i=0; i<H.size(); i++) if(H[i].ty) {
		p = i; c = H[i].ty;
		break;
	}
	int t = 0;
	if(!ct[1]) ++t;
	if(!ct[2]) ++t;
	if(p == -1) {
		ans = 1LL * hto * (hto - 1) + 2; ans %= MOD;
		ans *= get(tot - hto);
		printf("%lld", (ans + MOD - t) % MOD);
		return 0;
	}
	long long ans2 = 1;
	for(int i=p+1; i<=p+sz(H); i++) {
		int it = i % sz(H);
		if(H[it].ty) {
			if(H[it].ty == c) ans += 1LL * cnt * (cnt + 1) / 2, ans %= MOD;
			else ++ch, ans2 *= cnt + 1;
			c = H[it].ty;
			cnt = 0;
		}
		else ++cnt;
	}
	if(ch == 0) return !printf("%lld", ((ans + 1) * get(tot - hto) + MOD - t) % MOD);
	if(ch > 2) return !printf("0");
	ans2 %= MOD;
	printf("%lld", (ans2 * get(tot - hto) + MOD - t) % MOD);
	return 0;
}

Compilation message

constellation.cpp: In function 'int main()':
constellation.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<H.size(); i++) if(H[i].ty) {
               ~^~~~~~~~~
constellation.cpp: In function 'int CCW(star, star, star)':
constellation.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
constellation.cpp: In function 'int main()':
constellation.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
constellation.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &A[i].X, &A[i].Y, &A[i].ty);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.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 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 384 KB Output is correct

Subtask #2
10.0 / 10.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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #3
10.0 / 10.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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 256 KB Output is correct

Subtask #4
10.0 / 10.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 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #5
10.0 / 10.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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 256 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 4 ms 640 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 72 ms 1600 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 72 ms 1540 KB Output is correct
5 Correct 64 ms 3184 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 68 ms 5232 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 69 ms 1476 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 70 ms 1528 KB Output is correct
5 Correct 77 ms 3184 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 67 ms 5232 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 70 ms 1528 KB Output is correct
3 Correct 75 ms 3184 KB Output is correct
4 Correct 69 ms 3184 KB Output is correct
5 Correct 76 ms 3056 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 63 ms 5232 KB Output is correct
11 Correct 65 ms 5360 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 73 ms 1528 KB Output is correct
3 Correct 76 ms 1528 KB Output is correct
4 Correct 64 ms 3184 KB Output is correct
5 Correct 63 ms 3056 KB Output is correct
6 Correct 63 ms 3184 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 26 ms 2812 KB Output is correct