oj.uz

답안 #197614

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197614 2020-01-22T02:42:55 Z Sakamotoo Linear Garden (IOI08_linear_garden) C++17
100 / 100
 36 ms 10260 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;

#define mp make_pair
#define fi first
#define se second

//mt19937 rng(time(NULL)); //int
mt19937_64 rng(time(NULL)); //Long Long
//shuffle(a.begin(),a.end(),rng); //shuffle
//rng(); //random

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n;
	cin>>n;
	int m;
	cin>>m;
	string s;
	cin>>s;
	int l=0,r=0,now=0;
	long long pan[n+5];
	pan[0]=1;
	for(int i=1; i<=n; i++){
		pan[i]=(pan[i-1]*2)%m;
	}
	long long jaw=0;
	for(int i=0; i<s.size(); i++){
		if(s[i]=='P'){
			int sem=now+1;
			int x=l,y=r;
			y=max(sem,y);
//			cout<<"sem "<<sem<<endl;
			if(y-x>=3){
				jaw+=0;
			}else if(y-x==2){
				int mid=(y+x)/2;
				int jar=s.size()-i-1;
				if(sem!=mid) jar--;
				jaw+=pan[(jar+1)/2];
			}else {
				int z=y+1;
				int mid=(z+x)/2;
				int jar=s.size()-i-1;
				if(sem!=mid) jar--;
//				cout<<"jar "<<jar<<endl;
				jaw+=pan[(jar+1)/2];
				
				z=x-1;
				mid=(y+z)/2;
				jar=s.size()-i-1;
				if(sem!=mid) jar--;
				jaw+=pan[(jar+1)/2];
				
				jaw--;
			}
			now--;
			l=min(l,now);
//			cout<<jaw<<endl;
		}else {
			now++;
			r=max(r,now);
		}
	}
	jaw++;
//	cout<<jaw<<endl;
	cout<<jaw%m<<endl;
}

Compilation message

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:35:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.size(); i++){
               ~^~~~~~~~~

Subtask #1
2.0 / 2.0

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

Subtask #2
2.0 / 2.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
4.0 / 4.0

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

Subtask #7
4.0 / 4.0

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

Subtask #8
4.0 / 4.0

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

Subtask #9
4.0 / 4.0

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

Subtask #10
4.0 / 4.0

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

Subtask #11
4.0 / 4.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

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

Subtask #17
5.0 / 5.0

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

Subtask #18
5.0 / 5.0

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

Subtask #19
5.0 / 5.0

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

Subtask #20
5.0 / 5.0

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

Subtask #21
5.0 / 5.0

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

Subtask #22
5.0 / 5.0

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

Subtask #23
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 10244 KB Output is correct
2 Correct 35 ms 10260 KB Output is correct
3 Correct 36 ms 10232 KB Output is correct