Submission #501712

#	Time	Username	Problem	Language	Result	Execution time	Memory
501712		600Mihnea	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	96 ms	33656 KiB

linear_garden

#include <bits/stdc++.h>

using namespace std;


const int N = (int) 1e6 + 7;

int n;
int mod;
string s;

int whenStart[3][3][N];
int dp[3][3][N];
bool done[3][3];

void add(int i, int j, int k, int val) {
  assert(0 <= i && i < 3);
  assert(0 <= j && j <= i);
  assert(0 <= k && k <= n);
  dp[i][j][k] += val;
  if (dp[i][j][k] >= mod) {
    dp[i][j][k] -= mod;
  }
}

void compute(int init_dif, int init_current) {
  assert(init_current <= init_dif);
  if (done[init_dif][init_current]) return;
  done[init_dif][init_current] = 1;
  for (int d = 0; d < 3; d++) {
    for (int p = 0; p <= d; p++) {
      for (int i = 0; i <= n; i++) {
        dp[d][p][i] = 0;
      }
    }
  }
  dp[init_dif][init_current][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int dif = 0; dif < 3; dif++) {
      for (int pos = 0; pos <= dif; pos++) {
        if (int coef = dp[dif][pos][i]) {
          /// -1
          if (pos > 0) {
            add(dif, pos - 1, i + 1, coef);
          } else {
            if (dif + 1 <= 2) {
              add(dif + 1, 0, i + 1, coef);
            }
          }

          /// +1
          if (pos < dif) {
            add(dif, pos + 1, i + 1, coef);
          } else {
            if (dif + 1 <= 2) {
              add(dif + 1, dif + 1, i + 1, coef);
            }
          }
        }
      }
    }
  }
  for (int i = 0; i <= n; i++) {
    whenStart[init_dif][init_current][i] = 0;
    for (int dif = 0; dif < 3; dif++) {
      for (int pos = 0; pos <= dif; pos++) {
        whenStart[init_dif][init_current][i] += dp[dif][pos][i];
        if (whenStart[init_dif][init_current][i] >= mod) whenStart[init_dif][init_current][i] -= mod;
      }
    }
  }
}

int get(int dif, int current, int rem) {
  bool ok = (0 <= current && current <= dif && dif < 3);
  if (!ok) {
    return 0;
  }
  compute(dif, current);
  return whenStart[dif][current][rem];
}


signed main() {
  /// L < P

 ios::sync_with_stdio(0); cin.tie(0);

  ///freopen ("input", "r", stdin);

  cin >> n >> mod >> s;


  int dif = 0, pos = 0, cnt = 1;
  int rem = n;

  for (auto &ch : s) {
    int x;
    if (ch == 'L') {
      x = -1;
    } else {
      x = +1;
    }
    int X = pos, Y = dif;
    x = -1;
    if (x == -1) {
      if (pos > 0) {
        pos--;
      } else {
        dif++;
        pos = 0;
      }
    } else {
      if (pos < dif) {
        pos++;
      } else {
        dif++;
        pos = dif;
      }
    }
    rem--;
    if (ch == 'L') {
      x = -1;
    } else {
      cnt += get(dif, pos, rem);
      if (cnt >= mod) cnt -= mod;
      x = +1;
    }
    pos = X;
    dif = Y;
    if (x == -1) {
      if (pos > 0) {
        pos--;
      } else {
        dif++;
        pos = 0;
      }
    } else {
      if (pos < dif) {
        pos++;
      } else {
        dif++;
        pos = dif;
      }
    }
    assert(dif <= 2);
  }

  cout << cnt << "\n";

  return 0;
}

• 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