oj.uz

Submission #259448

# Submission time Handle Problem Language Result Execution time Memory
259448 2020-08-07T21:13:46 Z Namnamseo None (JOI12_constellation) C++17
100 / 100
 71 ms 5792 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};
	int ic[3] = {0, 0, 0};
	for (int i:hp) ++cnt[p[i].c], --ic[p[i].c];
	int inz = -cnt[0];
	rep(i, n) { ++ic[p[i].c]; if (!p[i].c) ++inz; }

	if (!cnt[1] && !cnt[2]) {
		int out = (hs * (hs-1ll) + 2) % mod;
		int in = pow2[inz];
		int ans = (out * 1ll * in % mod);
		ans = (ans + mod - !ic[1] - !ic[2]) % mod;
		cout << ans << 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 = 0;
		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;

		int exc = 1 + !cnt[1];
		ans += (pow2[inz] - !ic[3-exc]);
		ans %= mod;

		cout << ans << endl;
		return 0;
	}

	{ int bm = 0; 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:101:16: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  { int bm = 0; for (int i=hs-1; 0<=i; --i)
                ^~~
constellation.cpp:104: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
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 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 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 0 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 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 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 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 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 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 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 640 KB Output is correct
9 Correct 3 ms 640 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 56 ms 5220 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 54 ms 5220 KB Output is correct
5 Correct 53 ms 5772 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 53 ms 5768 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 54 ms 5220 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 55 ms 5348 KB Output is correct
5 Correct 53 ms 5768 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 52 ms 5700 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 58 ms 5220 KB Output is correct
3 Correct 51 ms 5768 KB Output is correct
4 Correct 71 ms 5644 KB Output is correct
5 Correct 53 ms 5652 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 51 ms 5644 KB Output is correct
11 Correct 52 ms 5644 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 55 ms 5220 KB Output is correct
3 Correct 53 ms 5220 KB Output is correct
4 Correct 54 ms 5644 KB Output is correct
5 Correct 53 ms 5772 KB Output is correct
6 Correct 54 ms 5792 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 23 ms 3080 KB Output is correct