oj.uz

Submission #113346

# Submission time Handle Problem Language Result Execution time Memory
113346 2019-05-25T06:39:09 Z MAMBA Park (BOI16_park) C++17
100 / 100
 694 ms 136848 KB 
#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<long 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 , i) {
			long double dx = x_[i] - x_[j];
			long double dy = y_[i] - y_[j];
			vec.pb({floor(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 , {-1 , i}});

	}

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

	for (auto e : vec) {
		if (e.second.first == -1) {
			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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 68636 KB Output is correct
2 Correct 474 ms 68532 KB Output is correct
3 Correct 488 ms 68636 KB Output is correct
4 Correct 519 ms 68636 KB Output is correct
5 Correct 523 ms 68508 KB Output is correct
6 Correct 501 ms 68552 KB Output is correct
7 Correct 470 ms 68636 KB Output is correct
8 Correct 483 ms 68640 KB Output is correct
9 Correct 4 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 11540 KB Output is correct
2 Correct 125 ms 11656 KB Output is correct
3 Correct 140 ms 11616 KB Output is correct
4 Correct 124 ms 11620 KB Output is correct
5 Correct 133 ms 11576 KB Output is correct
6 Correct 118 ms 11744 KB Output is correct
7 Correct 103 ms 10848 KB Output is correct
8 Correct 104 ms 10848 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 68636 KB Output is correct
2 Correct 474 ms 68532 KB Output is correct
3 Correct 488 ms 68636 KB Output is correct
4 Correct 519 ms 68636 KB Output is correct
5 Correct 523 ms 68508 KB Output is correct
6 Correct 501 ms 68552 KB Output is correct
7 Correct 470 ms 68636 KB Output is correct
8 Correct 483 ms 68640 KB Output is correct
9 Correct 4 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 131 ms 11540 KB Output is correct
12 Correct 125 ms 11656 KB Output is correct
13 Correct 140 ms 11616 KB Output is correct
14 Correct 124 ms 11620 KB Output is correct
15 Correct 133 ms 11576 KB Output is correct
16 Correct 118 ms 11744 KB Output is correct
17 Correct 103 ms 10848 KB Output is correct
18 Correct 104 ms 10848 KB Output is correct
19 Correct 635 ms 136792 KB Output is correct
20 Correct 676 ms 136740 KB Output is correct
21 Correct 641 ms 136664 KB Output is correct
22 Correct 644 ms 136664 KB Output is correct
23 Correct 694 ms 136792 KB Output is correct
24 Correct 667 ms 136848 KB Output is correct