제출 #963437

#제출 시각아이디문제언어결과실행 시간메모리
963437fzyzzz_zLinear Garden (IOI08_linear_garden)C++17
100 / 100
21 ms9172 KiB
#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 // }

컴파일 시 표준 에러 (stderr) 메시지

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])) {
      |              ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...