oj.uz

Submission #259637

# Submission time Handle Problem Language Result Execution time Memory
259637 2020-08-08T06:04:55 Z 송준혁(#5058) None (JOI12_constellation) C++17
0 / 100
 53 ms 2716 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;
	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[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; 
	}
	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;
	}
	else if (!c){
		int x=a;
		ans = 1;
		for (int i=x+1; i<=N; i++){
			if (A[i] == 1){
				ans = (ans + (i-x)*(i-x+1)/2) % MOD;
				x=i;
			}
		}
		ans = (ans + (N-b+a-1)*(N-b+a)/2) % MOD;
	}
	else{
		ans = ((c-b-1)*(c-b)/2+1)%MOD;
		if (!e) ans = ans * (((N-d+a-1)*(N-d+a)/2+1)%MOD) % MOD;
		else ans = ans * (((e-d-1)*(e-d)/2+1)%MOD) % 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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 1 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 53 ms 2716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -