Submission #86072

#	Time	Username	Problem	Language	Result	Execution time	Memory
86072		win11905	Linear Garden (IOI08_linear_garden)	C++11	100 / 100	24 ms	10704 KiB

linear_garden

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author win11905
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

const int N = 1e6+5;

class linear {
private:
	char A[N];
	int n, m, p2[N];
public:
	void solve(istream& cin, ostream& cout) {
    	cin >> n >> m;
    	cin >> A+1;
    	p2[0] = 1;
    	for(int i = 1; i <= n; ++i) p2[i] = (p2[i-1] * 2) % m;
    	int sum = 0, mx = 0, mn = 0, ans = 1;
    	for(int i = 1; i <= n; ++i) {
			if(A[i] == 'P' and sum - mn < 2) {
			    int nmx = max(mx, sum+1);
				int tod = n-i;
				if(nmx - mn == 2) {
					if(sum+1 != nmx) ans += p2[tod+1>>1];
					else ans += p2[tod>>1];
				} else
					ans += p2[tod>>1] + p2[tod+1>>1] - 1;
				ans %= m;
			}
			if(A[i] == 'P') mn = min(mn, --sum);
			else mx = max(mx, ++sum);
    	}
    	cout << ans << endl;
	}
};

class Solver {
public:
	void solve(std::istream& in, std::ostream& out) {
		linear *obj = new linear();
		obj->solve(in, out);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Solver solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Compilation message (stderr)

linear_garden.cpp: In member function 'void linear::solve(std::istream&, std::ostream&)':
linear_garden.cpp:28:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      cin >> A+1;
             ~^~
linear_garden.cpp:37:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      if(sum+1 != nmx) ans += p2[tod+1>>1];
                                 ~~~^~
linear_garden.cpp:40:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      ans += p2[tod>>1] + p2[tod+1>>1] - 1;
                             ~~~^~

• 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