oj.uz

Submission #98312

# Submission time Handle Problem Language Result Execution time Memory
98312 2019-02-22T06:02:56 Z shoemakerjo Linear Garden (IOI08_linear_garden) C++14
100 / 100
 253 ms 6528 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 432 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #11
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 428 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 548 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 764 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 892 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 2352 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2824 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 3488 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4220 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 6464 KB Output is correct
2 Correct 253 ms 6340 KB Output is correct
3 Correct 236 ms 6528 KB Output is correct