oj.uz

Submission #259449

# Submission time Handle Problem Language Result Execution time Memory
259449 2020-08-07T21:14:39 Z Namnamseo None (JOI12_constellation) C++17
100 / 100
 71 ms 2684 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

pp operator-(pp a,pp b){ return {a.x-b.x, a.y-b.y}; }
pair<pp,int> d[100010];
int n;
bool ccw(pp a, pp b){ return ll(b.y)*a.x-ll(b.x)*a.y>0; }
bool ccw(pp a, pp b, pp c){ return ccw(b-a, c-a); }

int hu[100010], hn;
int stk[100010], top;
void H(){
	top=1;
	for(int i=1; i<n; ++i){
		while(top>=2 && ccw(d[stk[top-2]].x, d[stk[top-1]].x, d[i].x)) --top;
		stk[top++] = i;
	}
	for(int i=0; i<top-1; ++i) hu[hn++]=d[stk[i]].y;
}

const ll m=1'000'000'007;
ll Ans(ll x){ ll r=1; for(;x--;) (r*=2)%=m; return r; }
ll Ans2(ll x){ return x*(x+1)/2%m;}

int main()
{
	read(n);
	int cnt[3]={0,0,0};
	for(int i=0; i<n; ++i){
		int a, b, c; read(a, b, c); d[i]={{a, b}, c}; ++cnt[c];
	}
	sort(d, d+n); H(); reverse(d, d+n); H();
	int hc[3]={0,0,0};
	for(int i=0; i<hn; ++i) ++hc[hu[i]];
	ll in=Ans(cnt[0]-hc[0]);
	int safe=int(!cnt[1])+!cnt[2];
	if(!hc[1] || !hc[2]){
		if(hc[0]==hn){
			printf("%lld\n", (in*(hn*(hn-1ll)%m+2)%m + m-safe) % m);
			return 0;
		}
		ll ans=1;
		int l=0, r=hn-1;
		while(!hu[l]) ++l; while(!hu[r]) --r;
		int cc=l+hn-1-r;
		for(int i=l; i<=r; ++i){
			if(hu[i]){
				(ans+=Ans2(cc))%=m; cc=0;
			} else ++cc;
		}
		printf("%lld\n", (in*ans%m + m-safe)%m);
		return 0;
	}
	rotate(hu,find(hu,hu+hn,1),hu+hn);
	int l=0, r=hn-1;
	while(hu[l]!=2) ++l; while(hu[r]!=2) --r;
	if(count(hu+l, hu+r+1, 1)){ puts("0"); return 0; }
	int cl=1, cr=1;
	while(l && !hu[l-1]) ++cl, --l;
	while(r+1<hn && !hu[r+1]) ++cr, ++r;
	printf("%lld\n", (in*cl%m*cr%m + m-safe) % m);
	return 0;
}

Compilation message

constellation.cpp: In function 'int main()':
constellation.cpp:56:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(!hu[l]) ++l; while(!hu[r]) --r;
   ^~~~~
constellation.cpp:56:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(!hu[l]) ++l; while(!hu[r]) --r;
                      ^~~~~
constellation.cpp:68:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  while(hu[l]!=2) ++l; while(hu[r]!=2) --r;
  ^~~~~
constellation.cpp:68:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  while(hu[l]!=2) ++l; while(hu[r]!=2) --r;
                       ^~~~~
constellation.cpp: In function 'void read(int&)':
constellation.cpp:6:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
constellation.cpp: In function 'void read(ll&)':
constellation.cpp:7:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                   ~~~~~^~~~~~~~~~~

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 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 0 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 0 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 #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 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 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 512 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 60 ms 2168 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 62 ms 2124 KB Output is correct
5 Correct 59 ms 2680 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 512 KB Output is correct
10 Correct 59 ms 2684 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 60 ms 2168 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 60 ms 2168 KB Output is correct
5 Correct 58 ms 2680 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 67 ms 2680 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 60 ms 2168 KB Output is correct
3 Correct 57 ms 2680 KB Output is correct
4 Correct 59 ms 2680 KB Output is correct
5 Correct 58 ms 2684 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 3 ms 512 KB Output is correct
10 Correct 59 ms 2680 KB Output is correct
11 Correct 58 ms 2680 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 62 ms 2168 KB Output is correct
3 Correct 61 ms 2168 KB Output is correct
4 Correct 57 ms 2680 KB Output is correct
5 Correct 71 ms 2680 KB Output is correct
6 Correct 60 ms 2680 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 37 ms 1920 KB Output is correct