Submission #98312

#	Time	Username	Problem	Language	Result	Execution time	Memory
98312		shoemakerjo	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	253 ms	6528 KiB

linear_garden

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int maxn = 1000010;
int N, M;

int smask[maxn]; //store mask of values or -1 if impossible

int cdp[1 << 5]; //stores the dp count (build right to left)
int ndp[1 << 5];

string gar;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;

	// M = 1000000000;

	cin >> gar;
	gar = " " + gar; //1-indexed

	int cmask = 0;
	cmask |= (1 << 2);

	for (int i = 1; i <= N; i++) {
		smask[i] = -1;

		if (gar[i] == 'P') {

			int om = cmask;
			if ((cmask & (1 << 4)) == 0) {
				om = om << 1;
				om |= (1 << 2);
				smask[i] = om;
			}
			cmask = cmask >> 1;
			cmask |= (1 << 2);
		}
		else {
			cmask = cmask << 1;
			cmask |= (1 << 2);
		}
	}

	cdp[1 << 2] = 1;
	int res = 0;
	for (int i = N; i >= 1; i--) {



		if (smask[i] >= 0) {

			bool h0 = smask[i] & (1 << 0);
			bool h1 = smask[i] & (1 << 1);
			bool h3 = smask[i] & (1 << 3);
			bool h4 = smask[i] & (1 << 4);
			bool ok;

			for (int j = 0; j < (1 << 5); j++) {
				ok = true;

				//try all other masks
				if (cdp[j] == 0) continue; //does not contribute
				if (h0) {
					if (j & (1 << 0)) {
						ok = false;
					}
					if (j & (1 << 1)) {
						ok = false;
					}
				}
				if (h1) {
					if (j & (1 << 0)) {
						ok = false;
					}
				}
				if (h3) {
					if (j & (1 << 4)) {
						ok = false;
					}
				}
				if (h4) {
					if (j & (1 << 4)) {
						ok = false;
					}
					if (j & (1 << 3)) {
						ok = false;
					}
				}

				if (ok) {

					// cout << "index " << i << ": "  << j << " \t:: " << cdp[j] << endl;
					res = (res + cdp[j])%M;
				}

			}
		}
		//update cdp 

		for (int j = 0; j < 32; j++) {
			ndp[j] = 0;
		}
		int nv;
		for (int j = 0; j < 32; j++) {
			//consider adding an L 
			if ( (j & (1 << 4)) == 0) {
				nv = j << 1;
				nv |= 1 << 2;
				ndp[nv] = (ndp[nv] + cdp[j])%M;
			}
			if ((j & (1 << 0)) == 0) {
				nv = j >> 1;
				nv |= 1 << 2;
				ndp[nv] = (ndp[nv] + cdp[j])%M;
			}
		}
		for (int j = 0; j < 32; j++) {


			cdp[j] = ndp[j];
		}

	}

	res = (res + 1)%M;
	cout << res << endl;


}

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5