| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 259640 |
2020-08-08T06:16:47 Z |
임성재(#5054) |
None (JOI12_constellation) |
C++17 |
|
5 ms |
384 KB |
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false);cin.tie(NULL)
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define eb emplace_back
#define em emplace
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const int inf = 1e9;
const ll Mod = inf + 7;
int n;
ll ans;
vector<pair<pll, int>> v;
ll x[100010];
ll y[100010];
int c[100010];
vector<int> st;
vector<ll> one, two;
ll cnt;
int color[100010];
ll ccw(pll a, pll b, pll c) {
return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}
int main() {
fast;
cin >> n;
for(int i=0; i<n; i++) {
cin >> x[i] >> y[i] >> c[i];
v.eb(mp(x[i], y[i]), c[i]);
if(!c[i]) cnt++;
}
sort(all(v));
sort(v.begin()+1, v.end(), [](pair<pll, int> a, pair<pll, int> b) {
return ccw(v[0].fi, a.fi, b.fi) < 0;
});
st.eb(0);
st.eb(1);
for(int i=2; i<v.size(); i++) {
while(st.size() >= 2) {
int s = st.back();
st.pop_back();
int f = st.back();
if(ccw(v[f].fi, v[s].fi, v[i].fi) < 0) {
st.eb(s);
break;
}
}
st.eb(i);
}
/*for(int i = 0; i < st.size(); i++) {
if(v[st[i]].se == 1) one.eb(i);
else if(v[st[i]].se == 2) two.eb(i);
else cnt--;
}
if(one.size() + two.size() == 0) {
ll k = st.size();
ans = k * (k-1) + 2;
ans %= Mod;
}
else if(two.size() == 0) {
ans++;
for(int i=1; i<one.size(); i++) {
ll k = one[i] - one[i-1] - 1;
ans += k * (k+1) / 2;
ans %= Mod;
}
ll k = (ll) st.size() + one[0] - one.back() - 1;
ans += k * (k+1) / 2;
ans %= Mod;
}
else if(one.size() == 0) {
ans++;
for(int i=1; i<two.size(); i++) {
ll k = two[i] - two[i-1] - 1;
ans += k * (k+1) / 2;
ans %= Mod;
}
ll k = (ll) st.size() + two[0] - two.back() - 1;
ans += k * (k+1) / 2;
ans %= Mod;
}
else if(one.front() < two.front()) {
bool flag = false;
ll l = two.front() - one.front();
ll r = (ll) st.size() + one.front() - two.back();
for(auto i : one) {
if(two.front() < i && i < two.back()) {
flag = true;
}
else if(i < two.front()) l = min(l, two.front() - i);
else if(i > two.back()) r = min(r, i - two.back());
}
if(!flag) {
ans = l * r % Mod;
}
}
else {
bool flag = false;
ll l = one.front() - two.front();
ll r = (ll) st.size() + two.front() - one.back();
for(auto i : two) {
if(one.front() < i && i < one.back()) {
flag = true;
}
else if(i < one.front()) l = min(l, one.front() - i);
else if(i > one.back()) r = min(r, i - one.back());
}
if(!flag) {
ans = l * r % Mod;
}
}
for(int i=0; i<cnt; i++) {
ans <<= 1;
ans %= Mod;
}*/
for(int i=0; i<(1<<n); i++) {
bool flag = false;
for(int j=0; j<n; j++) {
if((i & (1<<j)) && v[j].se == 1) flag = true;
if((~i & (1<<j)) && v[j].se == 2) flag = true;
color[j] = (i & (1 << j)) ? 2 : 1;
}
if(flag) continue;
int j = 0, k;
for( ; j < st.size() && color[st[0]] == color[st[j]]; j++);
for(k = j; k < st.size() && color[st[j]] == color[st[k]]; k++);
for(k; k<st.size(); k++) if(color[st[k]] != color[st[0]]) continue;
ans++;
}
cout << ans;
}
Compilation message
constellation.cpp: In function 'int main()':
constellation.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=2; i<v.size(); i++) {
~^~~~~~~~~
constellation.cpp:159:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( ; j < st.size() && color[st[0]] == color[st[j]]; j++);
~~^~~~~~~~~~~
constellation.cpp:160:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(k = j; k < st.size() && color[st[j]] == color[st[k]]; k++);
~~^~~~~~~~~~~
constellation.cpp:162:8: warning: statement has no effect [-Wunused-value]
for(k; k<st.size(); k++) if(color[st[k]] != color[st[0]]) continue;
^
constellation.cpp:162:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(k; k<st.size(); k++) if(color[st[k]] != color[st[0]]) continue;
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
