oj.uz

Submission #293366

# Submission time Handle Problem Language Result Execution time Memory
293366 2020-09-08T00:53:44 Z Hemimor Linear Garden (IOI08_linear_garden) C++14
100 / 100
 71 ms 10220 KB 
#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.0 / 2.0

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

Subtask #2
2.0 / 2.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
4.0 / 4.0

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

Subtask #7
4.0 / 4.0

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

Subtask #8
4.0 / 4.0

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

Subtask #9
4.0 / 4.0

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

Subtask #10
4.0 / 4.0

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

Subtask #11
4.0 / 4.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8192 KB Output is correct
2 Correct 12 ms 8164 KB Output is correct

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

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

Subtask #17
5.0 / 5.0

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

Subtask #18
5.0 / 5.0

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

Subtask #19
5.0 / 5.0

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

Subtask #20
5.0 / 5.0

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

Subtask #21
5.0 / 5.0

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

Subtask #22
5.0 / 5.0

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

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 10216 KB Output is correct
2 Correct 71 ms 10220 KB Output is correct
3 Correct 70 ms 10220 KB Output is correct