Submission #293366

#	Time	Username	Problem	Language	Result	Execution time	Memory
293366		Hemimor	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	71 ms	10220 KiB

linear_garden

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

const int M=1e6;
ll n,m,a[M];
string s;

ll g(ll x,ll N){
	if(N==0) return 1;
	if(x==0||x==2) return g(1,N-1);
	return a[(N+1)/2];
}

ll f(ll l,ll r,ll x,ll N){
	l=min(l,x);
	r=max(r,x);
	if(r-l>2) return 0;
	if(r-l==1) return (g(0,N)+g(1,N)-1+m)%m;
	return g(x-l,N);
}

int main(){
	a[0]=1;
	cin>>n>>m>>s;
	for(int i=1;i<M;i++) a[i]=a[i-1]*2%m;
	ll res=1,l=0,r=0,x=0;
	for(int i=0;i<n;i++){
		if(s[i]=='P'){
			ll tmp=f(l,r,x-1,n-i-1);
			(res+=tmp)%=m;
			x++;
		}
		else x--;
		l=min(l,x);
		r=max(r,x);
	}
	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