Submission #1245114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245114		nicolo_010	Fountain Parks (IOI21_parks)	C++20	5 / 100	86 ms	19420 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)

bool construct(v<int> &a, v<int> &b, v<int> &fa, v<int> &fb, v<pii> &ys, int pl) {
	int n = ys.size();
	bool can = true;
	rep(i, 0, n-1) {
		//cout << ys[i].first << " "<< ys[i+1].first << endl;
		a.push_back(ys[i].second);
		b.push_back(ys[i+1].second);
		if (ys[i+1].first-ys[i].first != 2) can = false;
		fa.push_back(pl);
		fb.push_back(ys[i].first+1);
	}
	return can;
}

int construct_roads(v<int> x, v<int> y) {
	int n = x.size();
	bool dos = false, cuatro = false;
	rep(i, 0, n) {
		if (x[i] == 2) dos = true;
		else if (x[i] == 4) cuatro = true;
	}
	v<int> a, b, fa, fb;
	if (dos && cuatro) {
		v<pii> ys2, ys4;
		rep(i, 0, n) {
			if (x[i] == 2) ys2.push_back({y[i], i});
			else ys4.push_back({y[i], i});
		}
		sort(ys2.begin(), ys2.end());
		sort(ys4.begin(), ys4.end());
		bool can1, can2;
		can1 = construct(a, b, fa, fb, ys2, 1);
		can2 = construct(a, b, fa, fb, ys4, 3);
		if (!(can1 && can2)) return 0;
		map<int, int> mp;
		rep(i, 0, (int)ys2.size()) {
			mp[ys2[i].first] = ys2[i].second;
		}
		bool can3 = false;
		rep(i, 0, (int)ys4.size()) {
			if (mp.count(ys4[i].first)) {
				can3 = true;
				a.push_back(mp[ys4[i].first]);
				b.push_back(ys4[i].second);
				fa.push_back(3);
				fb.push_back(ys4[i].first-1);
				break;
			}
		}
		if (!can3) return 0;
		build(a, b, fa, fb);
		return 1;
	}
	else if (dos) {
		v<pii> ys;
		rep(i, 0, n) {
			ys.push_back({y[i], i});
		}
		sort(ys.begin(), ys.end());
		bool can = construct(a, b, fa, fb, ys, 1);
		//cout << a.size() << " "<< b.size() << " "<< fa.size() << " " << fb.size() << endl;
		if (!can) return 0;
		build(a, b, fa, fb);
		return 1;
	}
	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