Submission #1099876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099876		model_code	Mosaic (IOI24_mosaic)	C++17	100 / 100	174 ms	22388 KiB

mosaic

// correct/arshia_solution.cpp

#include "mosaic.h"
#include <numeric>
#include <vector>
using namespace std;

const int S = 10;

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();
	vector<long long> C(Q, 0);

	vector<int> help(N - 1 << 1 | 1, 0);
	copy(Y.rbegin(), Y.rend(), help.begin());
	copy(X.begin() + 1, X.end(), help.begin() + N);

	for (int s = 0; s < S; s++) {
		vector<int> sum(N - s << 1, 0);
		partial_sum(help.begin(), help.end(), sum.begin() + 1);
		for (int i = 0; i < Q; i++)
			if (T[i] <= B[i] && L[i] <= R[i]) {
				if (T[i] == s)
					C[i] += sum[R[i] - T[i] + N - s] - sum[L[i] - T[i] + N - s - 1], T[i]++;
				if (L[i] == s)
					C[i] += sum[L[i] - T[i] + N - s] - sum[L[i] - B[i] + N - s - 1], L[i]++;
			}

		if (s == N - 1)
			return C;
		vector<int> nxt(N - s - 2 << 1 | 1, 0);
		for (int i = 0; i < N - s - 1; i++) {
			nxt[i + N - s - 2] = !help[i + N - s] && !(i ? nxt[i + N - s - 3] : help[N - s - 2]);
			nxt[N - s - 2 - i] = !help[N - s - i - 2] && !(i ? nxt[N - s - 1 - i] : help[N - s]);
		}
		help = nxt;
	}

	vector<long long> sum(N - S << 1, 0);
	partial_sum(help.begin(), help.end(), sum.begin() + 1), partial_sum(sum.begin(), sum.end(), sum.begin());
	for (int i = 0; i < Q; i++)
		if (T[i] <= B[i] && L[i] <= R[i])
			C[i] += sum[R[i] - T[i] + N - S] - sum[L[i] - T[i] + N - S - 1] - sum[R[i] - B[i] + N - S - 1] + (L[i] - B[i] + N - S - 2 >= 0 ? sum[L[i] - B[i] + N - S - 2] : 0);

	return C;
}

Compilation message (stderr)

mosaic.cpp: In function 'std::vector<long long int> mosaic(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
mosaic.cpp:14:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   14 |  vector<int> help(N - 1 << 1 | 1, 0);
      |                   ~~^~~
mosaic.cpp:19:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   19 |   vector<int> sum(N - s << 1, 0);
      |                   ~~^~~
mosaic.cpp:31:25: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   31 |   vector<int> nxt(N - s - 2 << 1 | 1, 0);
      |                   ~~~~~~^~~
mosaic.cpp:39:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |  vector<long long> sum(N - S << 1, 0);
      |                        ~~^~~

• 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: 22 / 22