oj.uz

답안 #963437

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963437 2024-04-15T03:19:51 Z fzyzzz_z Linear Garden (IOI08_linear_garden) C++17
100 / 100
 21 ms 9172 KB 
#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m; 
	cin >> n >> m; 

	vector<int> p(1000001); 
	p[0] = 1; 
	for (int i = 1; i <= 1000000; ++i) p[i] = (p[i - 1] * 2) % m; 

	vector<int> a(n, 0); 
	for (int i = 0; i < n; ++i) {
		char x; cin >> x;
		if (x == 'P') a[i] = 1; 
	}

	int ans = 0; 
	int v = 0; 

	for (int i = 0; i < n; ++i) {
		if (a[i] > v) { 
			int c = n - 1 - i; 
			ans += p[c / 2]; 
			if (i == 0 || (i > 0 && a[i] == a[i - 1])) {
				ans += p[(c + 1) / 2]; 
				ans -= 1; 
			}
			ans %= m; 
		} else if (i > 0 && (a[i] + a[i - 1] == 2) || (v == 2 && a[i - 1] < a[i])) {
			int c = n - 1 - i; 
			ans += p[c / 2]; 
			ans %= m; 
		}
		if (i > 0 && a[i] == a[i - 1]) v = 1 + a[i]; 

		// cout << ans << "\n";
	}

	cout << (ans + 1) % m << '\n';

	return 0; 
}

// BABBA

// case for starting B or BB, not just ABAB since it will make ABAA 
// { no AA/BB past yet 
// case 1: 
// B -> AA(BB)(BA).. or AB(AA)(BB)(AB)(AA)(BA) ... 

// case 2: 
// B -> A(BA)(BB)(AB)(AA)..  or A(BB)(AB)... 

// 1 overlap = ABABABABA...

// AB (at b) 
// ABB -> ABA(BB) or AB(AA)B .. 
// again 1 overlap 
// } 
// AA/BB seen already 
// { can only change the BB -> BA or AB -> AA
// only 2^(v/2) ways 
// }

Compilation message

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:35:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |   } else if (i > 0 && (a[i] + a[i - 1] == 2) || (v == 2 && a[i - 1] < a[i])) {
      |              ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

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

Subtask #2
2.0 / 2.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
4.0 / 4.0

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

Subtask #7
4.0 / 4.0

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

Subtask #8
4.0 / 4.0

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

Subtask #9
4.0 / 4.0

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

Subtask #10
4.0 / 4.0

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

Subtask #11
4.0 / 4.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

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

Subtask #17
5.0 / 5.0

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

Subtask #18
5.0 / 5.0

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

Subtask #19
5.0 / 5.0

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

Subtask #20
5.0 / 5.0

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

Subtask #21
5.0 / 5.0

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

Subtask #22
5.0 / 5.0

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

Subtask #23
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 9044 KB Output is correct
2 Correct 20 ms 9172 KB Output is correct
3 Correct 18 ms 9052 KB Output is correct