Submission #1254763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254763		testaccount	Mosaic (IOI24_mosaic)	C++20	78 / 100	257 ms	303120 KiB

mosaic

#include <bits/stdc++.h>
using namespace std;

string to_string(vector<int> numbers) {
	string text = "{";
	for (auto i = numbers.begin(); i != numbers.end(); i++) {
		text += to_string(*i);
		//if (next(i) != numbers.end()) {text += ", "}
	} text += '}';
	return text;
}
string to_string(vector<long long> numbers) {
	string text = "{";
	for (auto i = numbers.begin(); i != numbers.end(); i++) {
		text += to_string(*i);
		if (next(i) != numbers.end()) {text += " ";}
	} text += '}';
	return text;
}
string to_string(vector<vector<int>> numbers) {
	string text = "";
	for (auto i = numbers.begin(); i != numbers.end(); i++) {
		text += to_string(*i);
		if (next(i) != numbers.end()) {text += "\n";}
	} // text += '}';
	return text;
}
string to_string(vector<vector<long long>> numbers) {
	string text = "";
	for (auto i = numbers.begin(); i != numbers.end(); i++) {
		text += to_string(*i);
		if (next(i) != numbers.end()) {text += "\n";}
	} // text += '}';
	return text;
}
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
	int n = X.size(), q = T.size();
	
	bool areallzeros = true, bruteforcedone = false;
	for (int i = 0; i < n; i++) {if (X[i] != 0) {areallzeros = false; break;}}
	if (areallzeros) {for (int i = 0; i < n; i++) {if (Y[i] != 0) {areallzeros = false; break;}}}


	vector<vector<int>> hormatrix(3, vector<int>(n)), vermatrix(n, vector<int>(3));
	hormatrix[0] = X;
	
	vector<vector<int>> hormatrixprefix(3, vector<int>(n + 1, 0));
	vector<vector<int>> vermatrixprefix(3, vector<int>(n + 1, 0));

	if (!areallzeros) { //----------------------------------------------------
		for (int i = 0; i <= 2; i++) {
			hormatrix[i][0] = Y[i];
		} for (int i = 1; i <= 2; i++) {
			for (int j = 1; j < n; j++) {
				if (hormatrix[i - 1][j] == 0 && hormatrix[i][j - 1] == 0) {
					hormatrix[i][j] = 1;
				} else {hormatrix[i][j] = 0;}
			}
		} for (int j = 0; j <= 2; j++) {
			vermatrix[0][j] = X[j];
		} for (int i = 0; i < n; i++) {
			vermatrix[i][0] = Y[i];
		} for (int i = 1; i < n; i++) {
			for (int j = 1; j <= 2; j++) {
				if (vermatrix[i - 1][j] == 0 && vermatrix[i][j - 1] == 0) {
					vermatrix[i][j] = 1;
				} else {vermatrix[i][j] = 0;}
			}
		}


		for (int i = 0; i <= 2; i++) {
			hormatrixprefix[i][0] = 0;
			for (int j = 1; j < n + 1; j++) {
				hormatrixprefix[i][j] = hormatrixprefix[i][j - 1];
				if (hormatrix[i][j - 1] == 1) {hormatrixprefix[i][j]++;}
			}
		}
		for (int j = 0; j <= 2; j++) {
			vermatrixprefix[j][0] = 0;
			for (int i = 1; i < n + 1; i++) {
				vermatrixprefix[j][i] = vermatrixprefix[j][i - 1];
				if (vermatrix[i - 1][j] == 1) {vermatrixprefix[j][i]++;}
			}
		} //cout << to_string(hormatrixprefix) << endl << to_string(vermatrixprefix) << endl << endl << endl;

	} //----------------------------------------------------



	vector<long long> answers;

	
	vector<vector<int>> matrix;
	vector<vector<long long>> prefix;
	
	for (int i = 0; i < q; i++) {
		long long answ = 0;
		int top = T[i], bottom = B[i], left = L[i], right = R[i];
		

		if (areallzeros) {
			top = max(1, top);
			left = max(1, left);
			if (top <= bottom && left <= right) {
				if ((bottom - top + 1) % 2 == 0 || (right - left + 1) % 2 == 0) {
					answ = (long long)(bottom - top + 1) * (long long)(right - left + 1) / 2;
					//cout << '!';
				} else {
					if (top % 2 == left % 2) {
						answ = (long long)(bottom - top + 1) * (long long)(right - left + 1) / 2 + 1;
						//cout << (bottom - top + 1) * (right - left + 1) / 2 << endl;
						//cout << answ << endl;
					} else {
						answ = (long long)(bottom - top + 1) * (long long)(right - left + 1) / 2;
					}
				}
			} //cout << answ;
		} else if (top == bottom && left == right) {
			if (top > 2 && left > 2) {
				int minimum = min(top, left);
				top -= minimum - 2;
				left -= minimum - 2;
			} if (top <= 2) {
				answ = hormatrix[top][left];
			} else if (left <= 2) {
				answ = vermatrix[top][left];
			}
		}



		else if (top == bottom) {
			if (top <= 2) {
				answ = hormatrixprefix[top][right + 1] - hormatrixprefix[top][left];
			} else {
				if (left == 0) {answ += vermatrix[top][0]; left++;}
				if (left == 1 && right >= left) {answ += vermatrix[top][1]; left++;}
				if (right >= left) {
					int minimum = min(top, left);
					top -= minimum - 2;
					left -= minimum - 2;
					right -= minimum - 2;
					if (top == 2) {
						answ += hormatrixprefix[top][right + 1] - hormatrixprefix[top][left];
					} else {
						int temp = max(3, top - (right - left));
						int temp2 = max(0, right - left + 1 - (top - temp + 1));
						answ += vermatrixprefix[2][top + 1] - vermatrixprefix[2][temp];
						answ += hormatrixprefix[2][temp2 + 2] - hormatrixprefix[2][2];
					}
				}
			}
		} else if (n <= 5000 && top != bottom && !areallzeros) {
			if (!bruteforcedone) {
				bruteforcedone = true;

				matrix.resize(n, vector<int>(n));
				prefix.resize(n, vector<long long>(n, 0));

				matrix[0] = X;
				for (int i = 0; i < n; i++) {matrix[i][0] = Y[i];}
				//cout << to_string(matrix);
				for (int i = 0; i < n; i++) {
					vector<long long> prefixrow(n, 0);
					prefixrow[0] = matrix[i][0];
					for (int j = 0; j < n; j++) {
						
						if (i > 0 && j > 0) {
							if (matrix[i - 1][j] == 0 && matrix[i][j - 1] == 0) {
								matrix[i][j] = 1;
							} else {matrix[i][j] = 0;}
						}
						if (j > 0) {prefixrow[j] = prefixrow[j - 1] + matrix[i][j];}
						
						prefix[i][j] = prefixrow[j];
						if (i > 0) {prefix[i][j] += prefix[i - 1][j];}
						
					} /**/ //prefix[i] = prefixrow;
				} //cout << to_string(matrix) << endl << endl << to_string(prefix);
			}

			answ = prefix[bottom][right];
			if (top > 0) {answ -= prefix[top - 1][right];}
			if (left > 0) {answ -= prefix[bottom][left - 1];}
			if (top > 0 && left > 0) {answ += prefix[top - 1][left - 1];}
		}

		answers.push_back(answ);
	}
	
	//cout << answ << endl;
	//cout << to_string(hormatrix) << endl << endl << to_string(vermatrix);
	return answers;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 8 / 8
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19
• Subtask 8: 0 / 22