| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 259100 |
2020-08-07T08:03:02 Z |
반딧불(#5071) |
None (JOI12_constellation) |
C++17 |
|
74 ms |
4296 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
struct vector2{
ll x, y, col;
explicit vector2(double x_ = 0, double y_ = 0): x(x_), y(y_){}
bool operator==(const vector2 &r)const{
return x == r.x && y == r.y;
}
bool operator<(const vector2 &r)const{
return x != r.x ? x < r.x : y < r.y;
}
bool operator>(const vector2 &r)const{
return r < *this;
}
vector2 operator+(const vector2 &r)const{
return vector2(x+r.x, y+r.y);
}
vector2 operator-(const vector2 &r)const{
return vector2(x - r.x, y - r.y);
}
vector2 operator*(double r)const{
return vector2(x*r, y*r);
}
double norm() const { return hypot(x, y); }
ll dot(vector2 &r)const{
return x*r.x + y*r.y;
}
ll cross(vector2 &r)const{
return x*r.y - y*r.x;
}
};
ll ccw(vector2 a, vector2 b){
return a.cross(b);
}
ll ccw(vector2 a, vector2 b, vector2 c){
return ccw(b-a, c-a);
}
int n;
vector2 arr[100002];
ll power2[100002] = {1};
vector<int> hull;
ll ans;
vector<int> col;
int c1, c2;
int fc1, fc2;
void convexHull(){
sort(arr+1, arr+n+1);
sort(arr+2, arr+n+1, [&](const vector2 &a, const vector2 &b){
return ccw(a, arr[1], b) > 0;
});
hull.push_back(1);
for(int i=2; i<=n; i++){
while(hull.size() >= 2 && ccw(arr[hull[(int)hull.size()-2]], arr[hull[(int)hull.size()-1]], arr[i]) >= 0){
hull.pop_back();
}
hull.push_back(i);
}
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%lld %lld %lld", &arr[i].x, &arr[i].y, &arr[i].col);
power2[i] = power2[i-1] * 2 % MOD;
if(arr[i].col == 1) c1++;
else if(arr[i].col == 2) c2++;
}
fc1 = c1, fc2 = c2;
if(n==2){
int ans[3][3] = {{2, 1, 0}, {1, 1, 0}, {0, 0, 0}};
printf("%d\n", ans[c1][c2]);
return 0;
}
convexHull();
int k = (int)hull.size();
bool colExist = 0;
for(auto &x: hull){
vector2 tmp = arr[x];
if(tmp.col == 1) c1--, colExist = 1;
if(tmp.col == 2){
c2--;
if(!colExist) colExist = 2;
}
col.push_back(tmp.col);
}
if(!colExist) col[0] = 1;
else if(colExist == 2){
for(auto &x: col) if(x == 2) x = 1;
}
int pnt1 = 0;
for(int i=0; i<k; i++){
if(col[i] == 1){
pnt1 = i;
break;
}
if(i == k-1) return 1;
}
vector<int> tmpv (col.begin() + pnt1, col.end());
tmpv.insert(tmpv.end(), col.begin(), col.begin()+pnt1);
col = tmpv;
ll flipCnt = 0;
ll nowCol = 1;
vector<ll> zeroCnt;
vector<ll> realZeroCnt;
ll zeroCount = 0;
for(int i=0; i<=k; i++){
if(i == k || col[i] == 1){
if(zeroCount) zeroCnt.push_back(zeroCount+1);
if(nowCol == 2){
flipCnt++;
realZeroCnt.push_back(zeroCount+1);
nowCol = 1;
}
zeroCount = 0;
}
else if(col[i] == 2){
if(zeroCount) zeroCnt.push_back(zeroCount+1);
if(nowCol == 1){
flipCnt++;
realZeroCnt.push_back(zeroCount+1);
nowCol = 2;
}
zeroCount = 0;
}
else{
zeroCount++;
}
}
if(flipCnt > 2){
printf("0"); return 0;
}
if(flipCnt == 0){
ll sum = accumulate(zeroCnt.begin(), zeroCnt.end(), 0LL);
ll sum2 = 0;
for(auto &x: zeroCnt) sum2 += x*x;
ans = (sum * sum - sum2 + 1) % MOD;
}
else{
ans = 1;
for(auto &x: realZeroCnt) ans *= x, ans %= MOD;
}
ans *= power2[n - k - c1 - c2];
ans %= MOD;
if(fc1 == 0) ans--;
if(fc2 == 0) ans--;
if(ans < 0) ans += MOD;
printf("%lld", ans);
}
Compilation message
constellation.cpp: In function 'int main()':
constellation.cpp:104:22: warning: comparison of constant '2' with boolean expression is always false [-Wbool-compare]
else if(colExist == 2){
~~~~~~~~~^~~~
constellation.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
constellation.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld", &arr[i].x, &arr[i].y, &arr[i].col);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2688 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
2944 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
74 ms |
4216 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
2688 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
74 ms |
4296 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2688 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
