oj.uz

Submission #259443

# Submission time Handle Problem Language Result Execution time Memory
259443 2020-08-07T20:47:14 Z Namnamseo None (JOI12_constellation) C++17
0 / 100
 57 ms 5348 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void cppio(){ ios_base::sync_with_stdio(0); cin.tie(0); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define sz(x) (int)(x).size()
#define XY(p) p.x, p.y

struct pt {
	int x, y, c;
	bool operator<(const pt& r) const { return
		(x == r.x) ? (y<r.y) : (x<r.x); }
};

pt operator-(pt a, pt b) { return {a.x-b.x, a.y-b.y, 0}; }
bool ccw(pt a, pt b) { return b.y*1ll*a.x > a.y*1ll*b.x; }
bool ccw(pt a, pt b, pt c) { return ccw(b-a, c-a); }

vector<int> hull(vector<pt> v) {
	vector<int> ret;
	int s = 0, n = sz(v);
	rep(i, n) {
		while (s>=2 && ccw(
			v[ret[s-2]],
			v[ret[s-1]],
			v[i]
		)) --s, ret.pop_back();
		ret.pb(i); ++s;
	}

	return ret;
}

int n;
vector<pt> p;

int pow2[100010];
const int mod = int(1e9) + 7;

int main()
{
	cppio(); cin >> n;
	p.resize(n); for(auto &a:p) cin >> a.x >> a.y >> a.c;
	sort(all(p)); auto uh = hull(p);
	reverse(all(p)); auto dh = hull(p); for (int &x:dh) x=n-1-x;
	reverse(all(p));
	pow2[0] = 1; rrep(i, n) pow2[i] = (pow2[i-1]*2)%mod;

	vector<int> hp = uh;
	hp.insert(hp.end(), ++dh.begin(), --dh.end());
	int hs = sz(hp);

	int cnt[3] = {0, 0, 0};
	for (int i:hp) ++cnt[p[i].c];
	int inz = -cnt[0];
	rep(i, n) if (!p[i].c) ++inz;

	if (!cnt[1] && !cnt[2]) {
		cout << (((hs * (hs-1) + 2) * pow2[inz] % mod + mod - 2)%mod) << endl;
		return 0;
	}

	vector<int> cs(hs);
	rep(i, hs) cs[i] = p[hp[i]].c;
	{ int nz = 0; while (!cs[nz]) ++nz;
	rotate(cs.begin(), cs.begin()+nz, cs.end()); }

	if (!cnt[1] || !cnt[2]) {
		ll ans = 1;
		for (int i = 0; i < hs; ) {
			if (cs[i]) { ++i; continue; }
			int j = i;
			while (j<hs && !cs[j]) ++j;
			ll len = j-i;
			(ans += len * (len+1) / 2) %= mod;
			i = j;
		}
		ans = ans * pow2[inz] % mod;
		cout << ans << endl;
		return 0;
	}

	{ int bm = hs-1; for (int i=hs-1; 0<=i; --i)
		if (cs[i] == cs[0]) bm = i;
		else if (cs[i]) break;
		rotate(cs.begin(), cs.begin()+bm, cs.end()); }

	int lm = 0, fy = 0;
	rep(i, hs) {
		if (cs[i] == cs[0]) lm = i;
		else if (cs[i]) { fy = i; break; }
	}
	int ly = hs-1;
	while (!cs[ly]) --ly;

	for (int i=fy; i<ly; ++i) if (cs[i] == cs[0]) { cout << 0 << endl; return 0; }

	ll ans = (fy-lm) * 1ll * (hs-ly) % mod;
	ans = ans * pow2[inz] % mod;

	cout << ans << endl;

	return 0;
}

Compilation message

constellation.cpp: In function 'int main()':
constellation.cpp:91:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  { int bm = hs-1; for (int i=hs-1; 0<=i; --i)
                   ^~~
constellation.cpp:94:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   rotate(cs.begin(), cs.begin()+bm, cs.end()); }
   ^~~~~~

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Incorrect 1 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0.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 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.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 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.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 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 55 ms 5348 KB Output is correct
3 Incorrect 57 ms 5220 KB Output isn't correct
4 Halted 0 ms 0 KB -