Submission #888432

#	Time	Username	Problem	Language	Result	Execution time	Memory
888432		Hakiers	Crossing (JOI21_crossing)	C++17	26 / 100	7042 ms	11956 KiB

Main

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 2e5 + 7;
map<int, bool> mapa;
int GENE[MAXN][3];
int gen[MAXN][9];
int wzorzec[MAXN];
int n, q;

void generate(){
	
	// -(A+B)
	for(int i = 1; i <= n; i++)
		gen[i][0] = (-(GENE[i][0] + GENE[i][1]) + 6)%3;
	// -(A+C)
	for(int i = 1; i <= n; i++)
		gen[i][1] = (-(GENE[i][0] + GENE[i][2]) + 6)%3;
	// -(B+C)
	for(int i = 1; i <= n; i++)
		gen[i][2] = (-(GENE[i][1] + GENE[i][2]) + 6)%3;	
	// (A+B-C)
	for(int i = 1; i <= n; i++)
		gen[i][3] = ((GENE[i][0] + GENE[i][1] - GENE[i][2]) + 6)%3;	
	// (A-B+C)
	for(int i = 1; i <= n; i++)
		gen[i][4] = ((GENE[i][0] - GENE[i][1] + GENE[i][2]) + 6)%3;
	//(-A+B+C)
	for(int i = 1; i <= n; i++)
		gen[i][5] = ((-GENE[i][0] + GENE[i][1] + GENE[i][2]) + 6)%3;
	//default
	for(int i = 1; i <= n; i++){
		gen[i][6] = GENE[i][0];
		gen[i][7] = GENE[i][1];
		gen[i][8] = GENE[i][2];
	}	
}

void update(int a, int b, char c){
	int x;
	if(c == 'J') x = 0;
	else if(c == 'O') x = 1;
	else x = 2;
	
	for(int i = a; i <= b; i++)
		wzorzec[i] = x;
}

bool check(){
	for(int i = 0; i < 9; i++){
		bool can = 1;
		for(int j = 1; j <= n; j++)
			if(wzorzec[j] != gen[j][i]) can = 0;
	
		if(can) return true;
	}
	
	return false;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	string str;
	for(int i = 0; i <= 2; i++){
		cin >> str;
		
		for(int j = 0; j < n; j++){
			int a;
			if(str[j] == 'J') a = 0;
			else if(str[j] == 'O') a = 1;
			else a = 2;
			GENE[j+1][i] = a;
		}
	}
	generate();
	cin >> q;
	cin >> str;
	for(int i = 1; i <= n; i++){
		int a;
		if(str[i-1] == 'J') a = 0;
		else if(str[i-1] == 'O') a = 1;
		else a = 2;
		wzorzec[i] = a;
	}
	
	if(check()) cout << "Yes \n";
	else cout << "No \n";
	
	while(q--){
		int a, b;
		char c;
		cin >> a >> b >> c;
		update(a, b, c);
		if(check()) cout << "Yes \n";
		else cout << "No \n";
	}

}

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