Submission #1319932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319932		PieArmy	별자리 (JOI12_constellation)	C++20	100 / 100	46 ms	6596 KiB

constellation

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#define int ll

int mod=1e9+7;

int sum(int x,int y){
	if(x+y<mod)return x+y;
	return x+y-mod;
}

int sub(int x,int y){
	if(y)y=mod-y;
	return sum(x,y);
}

int mul(ll x,ll y){
	return (x*y)%mod;
}

int fpow(int x,int y=mod-2){
	int res=1;
	while(y>0){
		if(y&1)res=mul(res,x);
		x=mul(x,x);
		y>>=1;
	}
	return res;
}

int f(pair<int,int>x,pair<int,int>y){
	return x.fr*y.sc-x.sc*y.fr;
}

int n;
pair<pair<int,int>,int>arr[100023];
int var[100023],sira[100023],pref[2][100023];
vector<int>v;
int m=0;
int ans=1;

int32_t main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i].fr.fr>>arr[i].fr.sc>>arr[i].sc;
		arr[i].sc--;
	}
	sort(arr+1,arr+n+1);
	for(int i=1;i<=n;i++){
		if(var[i])continue;
		while(v.size()>1){
			if(f({arr[i].fr.fr-arr[v[m-2]].fr.fr,arr[i].fr.sc-arr[v[m-2]].fr.sc},
				{arr[v[m-1]].fr.fr-arr[i].fr.fr,arr[v[m-1]].fr.sc-arr[i].fr.sc})>=0){
				break;
			}
			var[v.back()]=0;
			v.pop_back();
			m--;
		}
		v.pb(i);
		m++;
		var[i]=1;
	}
	for(int i=n;i>=1;i--){
		if(var[i]&&i!=1)continue;
		while(v.size()>1){
			if(f({arr[i].fr.fr-arr[v[m-2]].fr.fr,arr[i].fr.sc-arr[v[m-2]].fr.sc},
				{arr[v[m-1]].fr.fr-arr[i].fr.fr,arr[v[m-1]].fr.sc-arr[i].fr.sc})>=0){
				break;
			}
			var[v.back()]=0;
			v.pop_back();
			m--;
		}
		v.pb(i);
		m++;
		var[i]=1;
	}
	v.pop_back();
	m--;
	int halve=fpow(2);
	for(int i=1;i<=m;i++){
		sira[i]=v[i-1];
		pref[0][i]=pref[0][i-1];
		pref[1][i]=pref[1][i-1];
		if(arr[sira[i]].sc!=-1){
			pref[arr[sira[i]].sc][i]++;
		}
	}
	if(pref[0][m]==0&&pref[1][m]==0){
		ans=sum(2,mul(m,m-1));
	}
	else if(pref[0][m]==0||pref[1][m]==0){
		ans=1;
		int i=1;
		while(arr[sira[i]].sc==-1)i++;
		int bas=i-1,cnt=0;
		for(;i<=m;i++){
			if(arr[sira[i]].sc==-1){
				cnt++;
				continue;
			}
			else if(cnt){
				ans=sum(ans,mul(mul(cnt+1,cnt),halve));
				cnt=0;
			}
		}
		cnt+=bas;
		ans=sum(ans,mul(mul(cnt+1,cnt),halve));
	}
	else{
		ans=0;
		int mn[2]={n+1,n+1},mx[2]={0,0};
		for(int i=1;i<=m;i++){
			if(arr[sira[i]].sc==-1)continue;
			mn[arr[sira[i]].sc]=min(i,mn[arr[sira[i]].sc]);
			mx[arr[sira[i]].sc]=i;
		}
		int a=0,b=0;
		if(pref[1][mn[0]]!=pref[1][mx[0]]&&pref[0][mn[1]]!=pref[0][mx[1]]){
			cout<<0<<endl;
			return 0;
		}
		else if(pref[1][mn[0]]!=pref[1][mx[0]]){
			for(int i=mx[1];i<=m;i++){
				if(arr[sira[i]].sc==0){
					mn[0]=i;
					break;
				}
			}
			for(int i=1;i<=mn[1];i++){
				if(arr[sira[i]].sc==0){
					mx[0]=i;
				}
			}
			a=mn[0]-mx[1];
			b=mn[1]-mx[0];
		}
		else if(pref[0][mn[1]]!=pref[0][mx[1]]){
			for(int i=mx[0];i<=m;i++){
				if(arr[sira[i]].sc==1){
					mn[1]=i;
					break;
				}
			}
			for(int i=1;i<=mn[0];i++){
				if(arr[sira[i]].sc==1){
					mx[1]=i;
				}
			}
			a=mn[0]-mx[1];
			b=mn[1]-mx[0];
		}
		else{
			a=max(mn[0],mn[1])-min(mx[0],mx[1]);
			b=m-max(mx[0],mx[1])+min(mn[0],mn[1]);
		}
		ans=sum(ans,mul(a,b));
	}
	int cnt[2]={0,0};
	for(int i=1;i<=n;i++){
		if(arr[i].sc==-1){
			if(var[i])continue;
			ans=mul(ans,2);
		}
		else cnt[arr[i].sc]++;
	}
	ans=sub(ans,sum(!cnt[0],!cnt[1]));
	cout<<ans<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10