Submission #197614

#	Time	Username	Problem	Language	Result	Execution time	Memory
197614		Sakamotoo	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	36 ms	10260 KiB

linear_garden

#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 (stderr)

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 / 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