oj.uz

답안 #428419

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428419 2021-06-15T11:36:38 Z jamielim Linear Garden (IOI08_linear_garden) C++14
100 / 100
 26 ms 10040 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n,m;
char str[1000005];
ll two[1000005];

ll dp(int x,int l,int h,int c){
	//printf("%d %d %d %d\n",x,l,h,c);
	if(h-l>2||c>=5||c<0)return 0;
	ll ans=0;
	if(h-l==2){
		if(c==(l+h)/2)ans=two[(x+1)/2];
		else ans=two[x/2];
	}else{ // 1
		ans=two[x/2]+two[(x+1)/2]-1;
	}
	return ans%m;
}

int main(){
	scanf("%d%d %s",&n,&m,str);
	two[0]=1;for(int i=1;i<1000005;i++)two[i]=(two[i-1]*2LL)%m;
	ll ans=0;
	int lo=2,hi=2,cur=2;
	for(int i=0;i<n;i++){
		if(str[i]=='L')cur++;
		else{
			ans+=dp(n-i-1,lo,max(cur+1,hi),cur+1);
			//printf("%lld\n",dp(n-i-1,lo,max(cur+1,hi),cur+1));
			cur--;
		}
		lo=min(cur,lo);hi=max(cur,hi);
		ans%=m;
	}
	printf("%lld",(ans+m+1)%m);
}

Compilation message

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d%d %s",&n,&m,str);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8012 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8012 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 8108 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8104 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8012 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8012 KB Output is correct

Subtask #7
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8012 KB Output is correct

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8012 KB Output is correct

Subtask #9
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8112 KB Output is correct

Subtask #10
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8012 KB Output is correct

Subtask #11
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8012 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8052 KB Output is correct
2 Correct 11 ms 8192 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 8044 KB Output is correct
2 Correct 10 ms 8064 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8012 KB Output is correct
2 Correct 9 ms 8140 KB Output is correct
3 Correct 9 ms 8140 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8140 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8116 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8188 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8220 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8740 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 8908 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 9036 KB Output is correct

Subtask #22
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 9292 KB Output is correct

Subtask #23
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 9972 KB Output is correct
2 Correct 20 ms 10000 KB Output is correct
3 Correct 22 ms 10040 KB Output is correct