Submission #113332

#	Time	Username	Problem	Language	Result	Execution time	Memory
113332		MAMBA	Park (BOI16_park)	C++17	0 / 100	7 ms	5760 KiB

park

#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
//#define mt make_tuple
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef complex<ld> point;
typedef pair<ld , ld> pld;
typedef vector<int> vi;

inline void fileIO(string s) {
	//	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 2e3 + 10;
constexpr int M = 1e5 + 10;

constexpr int MOD = 1e6 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

typedef pair<double, pii> pd;

int n, m;

double w , h , x_[N] , y_[N] , r_[N], r2_[M] , st[M];

vector<pd> vec;
vector<pii> should[4] =  {{},{{1,0},{2,0},{3,0}},{{0 ,2},{0 ,3},{1,2},{1,3}},{{3,0},{3,1},{3,2}}};

bool mat[4][4];

vi ans[M];
int par[N];
bitset<4> mt[N];

int get_par(int v) {
	if (!~par[v]) return v;
	return par[v] = get_par(par[v]);
}

inline void merge(int u , int v) {
	u = get_par(u);
	v = get_par(v);
	if (u == v) return;
	par[v] = u;
	mt[u] |= mt[v];
	rep(i , 0 , 4)
		rep(j , 0 , 4)
			if(mt[u][i] && mt[u][j])
					mat[i][j] = true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

#ifndef LOCAL
	//fileIO("superposition");
#endif

	memset(par , -1 , sizeof(par));

	cin >> n >> m >> w >> h;

	rep(i , 0 , 4)
		mt[n + i][i] = true;

	rep(i , 0 , n) {
		cin >> x_[i] >> y_[i] >> r_[i];
		vec.pb({y_[i] - r_[i] , {i , n}});
		vec.pb({ (w - x_[i]) - r_[i], {i , n + 1}});
		vec.pb({ (h - y_[i]) - r_[i] , {i , n + 2}});
		vec.pb({ x_[i] - r_[i], {i , n + 3}});

		rep(j , 0 , m) {
			double dx = x_[i] - x_[j];
			double dy = y_[i] - y_[j];
			vec.pb({sqrt(dx * dx + dy * dy) - r_[i] - r_[j] , {i , j}});
		}
	}

	rep(i , 0 , m) {
		cin >> r2_[i] >> st[i];
		st[i]--;
		vec.pb({r2_[i] * 2 , {1e9 , i}});

	}

	sort(vec.begin(), vec.end());

	for (auto e : vec) {
		if (e.second.first == 1e9) {
			int id = e.second.second;
			int me = st[id];

			int arr[4];
			rep(i , 0 , 4)
				arr[i] = (me + i) % 4;

			rep(i , 0 , 4) {
				bool flag = true;
				for (auto e_ : should[i])
					if (mat[arr[e_.first]][arr[e_.second]])
						flag = false;
				if (flag) ans[id].pb(arr[i]);
			}
		}
		else merge(e.second.first , e.second.second);
	}


	rep(i , 0 , m) {
		sort(all(ans[i]));
		for (auto e :ans[i])
			cout << e + 1;
		cout << '\n';
	}

	return 0;

}

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42