Submission #963437

#	Time	Username	Problem	Language	Result	Execution time	Memory
963437		fzyzzz_z	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	21 ms	9172 KiB

linear_garden

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

using ll = long long; 

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m; 
	cin >> n >> m; 

	vector<int> p(1000001); 
	p[0] = 1; 
	for (int i = 1; i <= 1000000; ++i) p[i] = (p[i - 1] * 2) % m; 

	vector<int> a(n, 0); 
	for (int i = 0; i < n; ++i) {
		char x; cin >> x;
		if (x == 'P') a[i] = 1; 
	}

	int ans = 0; 
	int v = 0; 

	for (int i = 0; i < n; ++i) {
		if (a[i] > v) { 
			int c = n - 1 - i; 
			ans += p[c / 2]; 
			if (i == 0 || (i > 0 && a[i] == a[i - 1])) {
				ans += p[(c + 1) / 2]; 
				ans -= 1; 
			}
			ans %= m; 
		} else if (i > 0 && (a[i] + a[i - 1] == 2) || (v == 2 && a[i - 1] < a[i])) {
			int c = n - 1 - i; 
			ans += p[c / 2]; 
			ans %= m; 
		}
		if (i > 0 && a[i] == a[i - 1]) v = 1 + a[i]; 

		// cout << ans << "\n";
	}

	cout << (ans + 1) % m << '\n';

	return 0; 
}

// BABBA

// case for starting B or BB, not just ABAB since it will make ABAA 
// { no AA/BB past yet 
// case 1: 
// B -> AA(BB)(BA).. or AB(AA)(BB)(AB)(AA)(BA) ... 

// case 2: 
// B -> A(BA)(BB)(AB)(AA)..  or A(BB)(AB)... 

// 1 overlap = ABABABABA...

// AB (at b) 
// ABB -> ABA(BB) or AB(AA)B .. 
// again 1 overlap 
// } 
// AA/BB seen already 
// { can only change the BB -> BA or AB -> AA
// only 2^(v/2) ways 
// }

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:35:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |   } else if (i > 0 && (a[i] + a[i - 1] == 2) || (v == 2 && a[i - 1] < a[i])) {
      |              ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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