Submission #406642

#	Time	Username	Problem	Language	Result	Execution time	Memory
406642		rqi	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	460 ms	2408 KiB

linear_garden

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

typedef long long ll;
typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()

void ckmin(int& a, int b){
	a = min(a, b);
}

void ckmax(int& a, int b){
	a = max(a, b);
}

int MOD;

struct mi{
	ll v;
	mi(){
		v = 0;
	}
	mi(ll _v){
		v = _v % MOD;
	}
};

mi& operator+=(mi& a, mi& b){
	a.v+=b.v;
	if(a.v >= MOD) a.v-=MOD;
	return a;
}

mi operator+(mi a, mi b){
	a+=b;
	return a;
}

const int mx = 1000005;
//map<pi, mi> dp[mx];
int highrang[5];
int lowrang[5];

int N;

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> MOD;
	string s;
	cin >> s;

	map<pair<pi, int>, mi> cur;
	map<pair<pi, int>, mi> ncur;

	cur[mp(mp(0, 0), 0)] = mi(1);
	//dp[0][mp(0, 0)] = mi(1);

	mi ans = mi(1);
	int pos = 0;

	for(int i = 1; i <= 2; i++){
		highrang[i] = lowrang[i] = N+5;
	}

	for(int i = 0; i < sz(s); i++){
		if(s[i] == 'L'){
			pos--;
			if(pos <= -1){
				ckmin(lowrang[-pos], i);
				//cout << "LOW " << i << "\n";
			}
		}
		else{
			pos++;
			if(pos >= 1){
				ckmin(highrang[pos], i);
				//cout << "HIGH " << i << "\n";
			}
		}
	}

	// for(int j = 1; j <= 2; j++){
	// 	cout << j << " " << lowrang[j] << " " << highrang[j] << "\n";
	// }

	for(int i = 1; i <= N; i++){
		//i-1 characters currently in dp
		//sz(s)-i index character in s to consider
		//cout << "i: " << i << "\n";
		

		if(s[sz(s)-i] == 'L'){
			pos-=(-1);
		}
		else{
			pos-=(1);
		}
		//cout << "pos: " << pos << "\n";
		if(s[sz(s)-i] == 'P'){
			pi bound = mp(0, 0);

			for(int j = 1; j <= 2; j++){
				if(sz(s)-i-1 >= highrang[j]){
					bound.s = j;
				}
				if(sz(s)-i-1 >= lowrang[j]){
					bound.f = -j;
				}
			}

			//cout << "bound: " << bound.f << " " << bound.s << "\n";

			int c_pos = pos-1; //add L
			for(auto u: cur){
				pi dp_bound = bound;
				ckmin(dp_bound.f, c_pos+u.f.f.f);
				ckmax(dp_bound.s, c_pos+u.f.f.s);
				if(dp_bound.s-dp_bound.f > 2) continue;
				ans+=u.s;
				//cout << "u.s.v: " << u.s.v << "\n";
			}
		}

		
		

		// cout << "i = " << i << "\n";
		ncur.clear();
		for(pair<pair<pi, int>, mi> z: cur){
			//pair<pair<pi, int>, mi> u = z;
			for(int j = -1; j <= 1; j+=2){
				auto u = z;
				int pos = u.f.s+j;
				ckmin(u.f.f.f, pos);
				ckmax(u.f.f.s, pos);
				if(u.f.f.s-u.f.f.f > 2) continue;
				ncur[mp(u.f.f, pos)]+=u.s;
			}
		}
		swap(cur, ncur);
		// for(auto u: cur){
		// 	dp[i][u.f.f]+=u.s;
		// }
		// for(auto u: cur){
		// 	cout << u.f.f.f << " " << u.f.f.s << " " << u.f.s << " " << u.s.v << "\n";
		// }
	}

	

	// pi bound = mp(0, 0);
	// int pos = 0;
	// mi ans = mi(1);
	// for(int i = 0; i < sz(s); i++){
	// 	if(s[i] == 'P'){
	// 		int c_pos = pos-1; //add L
	// 		for(auto u: dp[sz(s)-1-i]){
	// 			pi dp_bound = bound;
	// 			ckmin(dp_bound.f, c_pos+u.f.f);
	// 			ckmax(dp_bound.s, c_pos+u.f.s);
	// 			if(dp_bound.s-dp_bound.f > 2) continue;
	// 			ans+=u.s;
	// 		}
	// 	}

	// 	if(s[i] == 'L'){
	// 		pos--;
	// 	}
	// 	else{
	// 		pos++;
	// 	}
	// 	ckmin(bound.f, pos);
	// 	ckmax(bound.s, pos);
	// }

	cout << ans.v << "\n";
}

• 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