제출 #1243201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243201		santi3223	분수 공원 (IOI21_parks)	C++20	5 / 100	409 ms	57976 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < (ll)cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;
/*
static void check(bool cond, string message) {
	if (!cond) {
		printf("%s\n", message.c_str());
		fclose(stdout);
		exit(0);
	}
}

static int n;
static bool build_called;
static int m;
static vector<int> _u, _v, _a, _b;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
	check(!build_called, "build is called more than once");
	build_called = true;
	m = u.size();
	check(int(v.size()) == m, "u.size() != v.size()");
	check(int(a.size()) == m, "u.size() != a.size()");
	check(int(b.size()) == m, "u.size() != b.size()");
	_u = u;
	_v = v;
	_a = a;
	_b = b;
}


*/



int construct_roads(std::vector<int> x, std::vector<int> y){
	vector<pair<pll, ll>> coords;
	vector<int> a, b, u, v;
	map<pll, pll> mp;
	ll n = x.size();
	map<pll, bool> existe;
	ff(i, 0, n){
		existe[{y[i], x[i]}] = true;
		coords.pb({{y[i], x[i]}, i});
	}
	sort(all(coords));
	ff(i, 0, n){
		mp[{y[i], x[i]}] = {0, i};
	}
	if(n == 1){
		build(u, v, a, b);
		return 1;
	}
	ff(i, 0, n){
		ll cury = coords[i].fi.fi, curx = coords[i].fi.se, num = coords[i].se;
		if(!existe[{cury-2, curx}] && !existe[{cury+2, curx}] && !existe[{cury, curx-2}] && !existe[{cury, curx+2}]){
			//cout << "NOEXISTE " << curx << " " << cury << ed;
			return 0;
		}
		//horizontal
		if(curx == 2){
			if(existe[{cury, curx+2}]){
				if(mp[{cury, curx+2}].fi == 0){
					u.pb(mp[{cury, curx+2}].se);
					v.pb(num);
					mp[{cury, curx+2}].fi++;
					mp[{cury, curx}].fi++;
					a.pb(curx+1);
					b.pb(cury-1);
				}
			}
		}
		else{
			if(existe[{cury, curx-2}]){
				if(mp[{cury, curx-2}].fi == 0){
					u.pb(mp[{cury, curx-2}].se);
					v.pb(num);
					mp[{cury, curx-2}].fi++;
					mp[{cury, curx}].fi++;
					a.pb(curx-1);
					b.pb(cury-1);
				}
			}
		}
		//vertical
		if(existe[{cury+2, curx}]){
			u.pb(mp[{cury+2, curx}].se);
			v.pb(num);
			mp[{cury+2, curx}].fi++;
			mp[{cury, curx}].fi++;
			if(curx == 2){
				a.pb(curx-1);
				b.pb(cury+1);
			}
			else{
				a.pb(curx+1);
				b.pb(cury+1);
			}
		}
	}
	if(a.size() != n-1){
		return 0;
	}
	build(u, v, a, b);
	return 1;
}





/*
int main() {
	assert(scanf("%d", &n) == 1);
	vector<int> x(n), y(n);
	for (int i = 0; i < n; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	build_called = false;
	const int possible = construct_roads(x, y);

	check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
	if (possible == 1) {
		check(build_called, "construct_roads() returned 1 without calling build()");
	} else {
		check(!build_called, "construct_roads() called build() but returned 0");
	}

	printf("%d\n", possible);
	if (possible == 1) {
		printf("%d\n", m);
		for (int j = 0; j < m; j++) {
			printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
		}
	}
	fclose(stdout);
	return 0;
}
*/

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30