Submission #343308

#	Time	Username	Problem	Language	Result	Execution time	Memory
343308		keta_tsimakuridze	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	70 ms	6388 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n, mod, s, ans, pwr[N];
map<int,int> fix;
string a;
bool ok(){
	if(abs(s) > 2) return 0;
	if( fix[-2] && fix[1] + fix[2]) return 0;
	if( fix[2] && fix[-1] ) return 0;
	return 1;
}
int main() {
	cin >> n >> mod;
	cin >> a;
	a = '$' + a;
	pwr[0] = 1;
	for(int i=1; i<=n; i++)
	pwr[i] = pwr[i-1] * 2 % mod;
	for(int i=1; i<=n; i++) {
		if ( a[i] == 'P' ){
			s -- ; fix[s] ++;
			if ( ok() ) {
				if ( fix[2] || fix[-2]) {
					if ( abs(s) == 1) ans += pwr [ (n - i + 1)/2];
					else ans += pwr [ (n - i)/2];		
				}
				else {
					if( fix[-1]  && fix [1]){
						
						if (!s) ans += pwr [ (n - i + 1)/2];
						else ans +=pwr [ (n - i)/2];
					}
					else {
				    ans += (pwr [ (n - i + 1)/2] + pwr [ (n - i )/2] - 1 + mod) % mod;
					}
				}
				ans %=mod;
			}
			fix[s] --;
			s += 2;
		}
		else s --;
		fix [s] ++;
	}
	cout << (ans + 1)%mod ;
}

• 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