oj.uz

Submission #259650

# Submission time Handle Problem Language Result Execution time Memory
259650 2020-08-08T06:35:42 Z 송준혁(#5058) None (JOI12_constellation) C++17
90 / 100
 65 ms 7928 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define Mup(a,x) a=max(a, x)
#define mup(a,x) a=min(a, x)
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define INF (1ll<<60)
#define MOD 1'000'000'007 
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N;
int A[101010];
LL ans;

struct pt{
	LL x, y, c;
	pt operator-(const pt &r)const{return (pt){x-r.x, y-r.y, 0};}
	LL operator*(const pt &r)const{return x*r.y-y*r.x;}
} P[101010];
vector<pt> V;

int main(){
	scanf("%d", &N);
	int qm=0, c1=0, c2=0;
	for (int i=1; i<=N; i++){
		scanf("%lld %lld %lld", &P[i].x, &P[i].y, &P[i].c);
		if (P[i].c == 0) qm++;
		if (P[i].c == 1) c1=1;
		if (P[i].c == 2) c2=1;
		if (P[1].x > P[i].x) swap(P[1], P[i]);
	}
	sort(P+2, P+N+1, [&](pt a, pt b){return (a-P[1])*(b-P[1])>0;});
	V.pb(P[1]), V.pb(P[2]);
	for (int i=3; i<=N; i++){
		while ((V.back()-V[V.size()-2])*(P[i]-V.back())<0) V.pop_back();
		V.pb(P[i]);
	}
	N = V.size();
	for (int i=0; i<N; i++) A[i+1] = V[i].c;
	LL cqm=0, a=0, b=0, c=0, d=0, e=0;
	for (int i=1; i<=N; i++){
		if (!A[i]) cqm++;
		else if (!a) a=A[i], A[i]=1;
		else A[i]=(A[i]==a)?1:2; 
	}
	if (a == 2) swap(c1, c2);
	a=0;
	for (int i=1; i<=N; i++){
		if (A[i] == 1){
			if (!a) a=b=i;
			else if (!c) b=i;
			else if (!e) e=i;
		}
		if (A[i] == 2){
			if (!c) c=d=i;
			else if (!e) d=i;
			else{
				printf("0\n");
				return 0;
			}
		}
	}
	if (!a){
		ans = (LL)N*(N-1)%MOD;
		ans = (ans+2)%MOD;
		for (int i=1; i<=qm-cqm; i++) ans=ans*2%MOD;
		if (!c1) ans = (ans-1+MOD)%MOD;
		if (!c2) ans = (ans-1+MOD)%MOD;
	}
	else if (!c){
		int x=a;
		ans = 1;
		for (int i=x+1; i<=N; i++){
			if (A[i] == 1){
				ans = (ans + (i-x-1)*(i-x)/2) % MOD;
				x=i;
			}
		}
		ans = (ans + (N-b+a-1)*(N-b+a)/2) % MOD;
		for (int i=1; i<=qm-cqm; i++) ans=ans*2%MOD;
		if (!c2) ans = (ans-1+MOD)%MOD;
	}
	else{
		ans = c-b;
		if (!e) ans = ans * (N-d+a) % MOD;
		else ans = ans * (e-d) % MOD;
		for (int i=1; i<=qm-cqm; i++) ans=ans*2%MOD;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

constellation.cpp: In function 'int main()':
constellation.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
constellation.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld", &P[i].x, &P[i].y, &P[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 384 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 384 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 384 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 3 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 768 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 59 ms 2680 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 57 ms 2680 KB Output is correct
5 Correct 59 ms 7928 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 4 ms 896 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 57 ms 7916 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 65 ms 2684 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 57 ms 4728 KB Output is correct
5 Correct 58 ms 7916 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 57 ms 7916 KB Output is correct

Subtask #9
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 56 ms 2808 KB Output is correct
3 Correct 56 ms 5872 KB Output is correct
4 Correct 58 ms 5896 KB Output is correct
5 Correct 56 ms 5868 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Incorrect 57 ms 7788 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 59 ms 2808 KB Output is correct
3 Correct 56 ms 2780 KB Output is correct
4 Correct 57 ms 7788 KB Output is correct
5 Correct 58 ms 7916 KB Output is correct
6 Correct 58 ms 7916 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 23 ms 4084 KB Output is correct