oj.uz

답안 #259640

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259640 2020-08-08T06:16:47 Z 임성재(#5054) 별자리 (JOI12_constellation) C++17
0 / 100
 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;
          ~^~~~~~~~~~

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -