Submission #107740

#TimeUsernameProblemLanguageResultExecution timeMemory
107740luciocfLinear Garden (IOI08_linear_garden)C++14
100 / 100
859 ms2468 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6+10; const int delta = 5; int n, mod; // pos, dif, Max L-R, Max R-L, Prefixo/menor // -1 -> 4 // -2 -> 3 int dp[2][5][3][3][2]; char s[maxn]; bool bad(int dif, int mx) { if (dif > 2 || (dif == 2 && mx > 0) || (dif == 1 && mx > 1)) return 1; return 0; } void add(int &a, int &b) { a = (a+b)%mod; } void init(int cur) { for (int j = 0; j < 5; j++) for (int l = 0; l < 3; l++) for (int p = 0; p < 3; p++) for (int m = 0; m < 2; m++) dp[cur][j][l][p][m] = 0; } int main(void) { scanf("%d %d", &n, &mod); for (int i = 1; i <= n; i++) scanf(" %c", &s[i]); if (s[1] == 'L') dp[1][1][1][0][1] = 1; else { dp[1][-1+delta][0][1][1] = 1; dp[1][1][1][0][0] = 1; } for (int i = 1; i < n; i++) { int cur = (i+1)%2, ant = i%2; init(cur); for (int j = 0; j < 5; j++) { for (int l = 0; l < 3; l++) { for (int p = 0; p < 3; p++) { for (int m = 0; m < 2; m++) { int dif = (j <= 2 ? j : abs(j-delta)); if (j <= 2 && bad(dif, p)) continue; if (j > 2 && bad(dif, l)) continue; // colocar L if ((j > 2 && !bad(dif-1, l)) || !bad(dif+1, p)) { int e; if (m == 0 || s[i+1] == 'P') e = 0; else e = 1; if (j > 2) { int newdif = (j == 3 ? 4 : 0); add(dp[cur][newdif][l][p][e], dp[ant][j][l][p][m]); } else { int newdif = dif+1, newmax = max(l, newdif); add(dp[cur][newdif][newmax][p][e], dp[ant][j][l][p][m]); } } // colocar P if ((j > 0 && j <= 2 && !bad(dif-1, p)) || !bad(dif+1, l)) { if (m && s[i+1] == 'L') continue; int e = m; if (j == 0) { int newdif = 4, newmax = max(p, 1); add(dp[cur][newdif][l][newmax][e], dp[ant][j][l][p][m]); } else if (j <= 2) { int newdif = dif-1; add(dp[cur][newdif][l][p][e], dp[ant][j][l][p][m]); } else { int newdif = 3, newmax = max(p, dif+1); add(dp[cur][newdif][l][newmax][e], dp[ant][j][l][p][m]); } } } } } } } int ans = 0; for (int j = 0; j < 5; j++) for (int l = 0; l < 3; l++) for (int p = 0; p < 3; p++) add(ans, dp[n%2][j][l][p][0]); ans = (ans+1)%mod; printf("%d\n", ans); }

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &mod);
  ~~~~~^~~~~~~~~~~~~~~~~~~
linear_garden.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &s[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...