oj.uz

Submission #416349

# Submission time Handle Problem Language Result Execution time Memory
416349 2021-06-02T10:34:48 Z model_code Parking Problem (innopolis2021_final_A) C++17
0 / 100
 3000 ms 2716 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3091 ms 1604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 2716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 708 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3091 ms 1604 KB Time limit exceeded
2 Halted 0 ms 0 KB -