oj.uz

답안 #86072

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
86072 2018-11-24T14:39:02 Z win11905 Linear Garden (IOI08_linear_garden) C++11
100 / 100
 24 ms 10704 KB 
/**
 * 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

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.0 / 2.0

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

Subtask #2
2.0 / 2.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
4.0 / 4.0

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

Subtask #7
4.0 / 4.0

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

Subtask #8
4.0 / 4.0

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

Subtask #9
4.0 / 4.0

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

Subtask #10
4.0 / 4.0

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

Subtask #11
4.0 / 4.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

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

Subtask #17
5.0 / 5.0

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

Subtask #18
5.0 / 5.0

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

Subtask #19
5.0 / 5.0

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

Subtask #20
5.0 / 5.0

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

Subtask #21
5.0 / 5.0

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

Subtask #22
5.0 / 5.0

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

Subtask #23
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 8744 KB Output is correct
2 Correct 22 ms 9724 KB Output is correct
3 Correct 24 ms 10704 KB Output is correct