Submission #742637

#	Time	Username	Problem	Language	Result	Execution time	Memory
742637		ToniB	Crossing (JOI21_crossing)	C++17	26 / 100	7063 ms	8216 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 2;

int n, q;
bool ans[MAXN];
struct Change {
	int l, r;
	char c;
} a[MAXN];
string poc[3];
string t;

string comp(string& a, string& b){
	string ret = "";
	for(int i = 0; i < n; ++i){
		if(a[i] == b[i]) ret += a[i];
		else for(char c : {'J', 'O', 'I'}){
			if(c != a[i] && c != b[i]) ret += c;
		}
	}
	return ret;
}

void solve(string s){
	string cur = t;
	ans[0] |= (s == cur);
	for(int i = 1; i <= q; ++i){
		for(int j = a[i].l; j <= a[i].r; ++j){
			cur[j] = a[i].c;
		}
		ans[i] |= (s == cur);
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n;
	for(int i = 0; i < 3; ++i) cin >> poc[i];
	cin >> q >> t;
	for(int i = 1; i <= q; ++i){
		cin >> a[i].l >> a[i].r >> a[i].c;
		--a[i].l, --a[i].r;
	}
	for(int i = 1; i < 8; ++i){
		string cur = "";
		vector<int> tmp;
		for(int j = 0; j < 3; ++j){
			if(i & 1 << j){
				tmp.push_back(j);
			}
		}
		do{
			cur = poc[tmp[0]];
			for(int j = 1; j < (int)tmp.size(); ++j) cur = comp(cur, poc[tmp[j]]);
			solve(cur);
		} while(next_permutation(tmp.begin(), tmp.end()));
	}
	for(int i = 0; i <= q; ++i){
		if(ans[i]) cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 23
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51