Submission #416368

#	Time	Username	Problem	Language	Result	Execution time	Memory
416368		model_code	Long puzzle (innopolis2021_final_D)	C++17	80 / 100	3045 ms	10880 KiB

Main

// Created by Nikolay Budin

#ifdef DEBUG
#  define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ff first
#define ss second
#define szof(x) ((int)x.size())
#ifndef LOCAL
#  define cerr __get_ce
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;

using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K, typename V> using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }

const int MOD = 1'000'000'007;

void add(int& a, int b) {
	a += b;
	if (a >= MOD) {
		a -= MOD;
	}
}

ll encode(int len, int deg1, int deg2, int mask_have, vector<int> const& color) {
	ll ret = len;
	ret <<= 11;
	ret |= deg1 + 1000;
	ret <<= 11;
	ret |= deg2 + 1000;
	ret <<= 4;
	ret |= mask_have;
	for (int i = 0; i < 4; ++i) {
		ret <<= 2;
		ret |= color[i];
	}
	return ret;
}

void decode(ll val, int& len, int& deg1, int& deg2, int& mask_have, vector<int>& color) {
	for (int i = 3; i >= 0; --i) {
		color[i] = val & 3;
		val >>= 2;
	}
	mask_have = val & 15;
	val >>= 4;
	deg2 = (val & 2047) - 1000;
	val >>= 11;
	deg1 = (val & 2047) - 1000;
	val >>= 11;
	len = val;
}

void solve() {
	int n, l;
	cin >> n >> l;
	// len, deg_in[1] - deg_out[1], deg_in[2] - deg_out[2], mask_have, color_0 .. color_3

	vector<pair<ll, int>> vars, next;
	vars.push_back({encode(0, 0, 0, 0, {0, 1, 2, 3}), 1});

	int len, deg1, deg2, mask_have;
	vector<int> color(4);


	for (int it = 0; it < n; ++it) {
		int a;
		string b, c;
		cin >> a >> b >> c;
		int vl, vr;
		if (b == "none") {
			vl = 0;
		} else if (b == "in") {
			vl = 1;
		} else {
			vl = 2;
		}
		if (c == "none") {
			vr = 3;
		} else if (c == "in") {
			vr = 2;
		} else {
			vr = 1;
		}

		// cerr << szof(vars) << endl;

		next.clear();

		for (auto p : vars) {
			decode(p.ff, len, deg1, deg2, mask_have, color);
			// cerr << len << " " << deg1 << " " << deg2 << " " << mask_have << endl;
			next.push_back(p);

			if (len + a > l || (vl == 0 && (mask_have & 1)) || (vr == 3 && (mask_have & 8))) {
				continue;
			}

			len += a;

			mask_have |= 1 << vl;
			mask_have |= 1 << vr;
			if (vl == 1) {
				--deg1;
			}
			if (vl == 2) {
				--deg2;
			}
			if (vr == 1) {
				++deg1;
			}
			if (vr == 2) {
				++deg2;
			}

			if (color[vl] != color[vr]) {
				int old_color = color[vr];
				replace(color.begin(), color.end(), old_color, color[vl]);
				int color_cnt = 0;
				for (int i = 0; i < 4; ++i) {
					if (find(color.begin(), color.begin() + i, color[i]) == color.begin() + i) {
						if (color[i] != color_cnt) {
							old_color = color[i];
							replace(color.begin(), color.end(), old_color, color_cnt);
						}
						++color_cnt;
					}
				}
			}

			next.push_back({encode(len, deg1, deg2, mask_have, color), p.ss});
		}

		sort(next.begin(), next.end());
		vars.clear();
		for (auto p : next) {
			if (!szof(vars) || vars.back().ff != p.ff) {
				vars.push_back(p);
			} else {
				add(vars.back().ss, p.ss);
			}
		}
	}

	int ans = 0;
	for (auto p : vars) {
		decode(p.ff, len, deg1, deg2, mask_have, color);
		if (len == l && deg1 == 0 && deg2 == 0 && (mask_have & 1) && (mask_have & 8) 
			&& color[3] == 0 && (!(mask_have & 2) || color[1] == 0) && (!(mask_have & 4) || color[2] == 0)) {
			add(ans, p.ss);
		}
	}

	cout << ans << "\n";
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}

#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20