Submission #416349

#	Time	Username	Problem	Language	Result	Execution time	Memory
416349		model_code	Parking Problem (innopolis2021_final_A)	C++17	0 / 100	3091 ms	2716 KiB

Main

#include <bits/stdc++.h>

/**
 * Author: Niyaz Nigmatullin
 */

using namespace std;

bool noplace(string const &s) {
	for (int i = 0; i + 1 < (int) s.size(); i++) {
		if (s[i] == '.' && s[i + 1] == '.') return false;
	}
	return true;
}

bool check(string &p, int cars, int moto) {
	if (noplace(p)) {
		return true;
	}
	for (int i = 0; i < (int) p.size(); i++) {
		if (p[i] == '.' && moto > 0) {
			p[i] = 'X';
			bool res = check(p, cars, moto - 1);
			p[i] = '.';
			if (res) return true;
		}
		if (i + 1 < (int) p.size() && p[i] == '.' && p[i + 1] == '.' && cars > 0) {
			p[i] = 'X';
			p[i + 1] = 'X';
			bool res = check(p, cars - 1, moto);
			p[i] = '.';
			p[i + 1] = '.';
			if (res) return true;
		}
	}
	return false;
}

void solve() {
	string parking, waiting;
	cin >> parking >> waiting;
	int l = -1;
	int r = (int) waiting.size() + 1;
	while (l < r - 1) {
		int mid = (l + r) >> 1;
		int cars = 0;
		int moto = 0;
		for (int i = 0; i < mid; i++) {
			if (waiting[i] == 'C') ++cars; else ++moto;
		}
		string copy = parking;
		if (check(copy, cars, moto)) {
			r = mid;
		} else {
			l = mid;
		}
	}
	for (int i = 0; i <= l; i++) cout << 'Y';
	for (int i = l + 1; i <= (int) waiting.size(); i++) cout << 'N';
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin >> t;
	while (t--) solve();
}

• Subtask 1: 0 / 31
• Subtask 2: 0 / 22
• Subtask 3: 0 / 23
• Subtask 4: 0 / 24