Submission #1326032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326032		SonicML	Linear Garden (IOI08_linear_garden)	C++20	95 / 100	57 ms	37676 KiB

linear_garden

#include <iostream>

using namespace std;

int modulo;

int const NMAX = 1e6;
int dp[1 + NMAX][3][3];

int main() {

  int n;
  cin >> n >> modulo;
  for(int i = 0;i < 3;i++) {
    for(int j = 0;j < 3;j++) {
      dp[0][i][j] = 0;
    }
  }
  dp[0][0][0] = 1;
  dp[0][1][1] = 1;
  dp[0][2][2] = 1;
  for(int i = 1;i <= n;i++) {
    for(int k = 0;k < 3;k++) {
      for(int j = 0;j < 3;j++) {
        if(j > 0) {
          dp[i][k][j] += dp[i-1][k][j-1];
        }
        if(j < 2) {
          dp[i][k][j] += dp[i-1][k][j+1];
        }
        dp[i][k][j] %= modulo;
      }
    }
  }
  string s;
  cin >> s;
  int presum = 0;
  int ans = 0;
  bool badPlus2 = false, badMinus2 = false, badNega = false, badPosi = false;
  bool nbp2, nbm2, nbn, nbp;
  bool gSign, gPosi, gNega;
  for(int i = 0;i < s.size();i++) {
    if(s[i] == 'P') {
      int tempsum = presum + 1;
      if((-2 <= tempsum && tempsum <= 2) && 
        !(badPlus2 && tempsum == 2) && !(badMinus2 && tempsum == -2) && !(badNega && tempsum < 0) && !(badPosi && tempsum > 0)) {
        // it's okay to replace P with L here
        // get the new legal ranges in place
        nbp2 = (badPlus2 || (tempsum < 0));
        nbm2 = (badMinus2 || (tempsum > 0));
        nbn = (badNega || (tempsum == 2));
        nbp = (badPosi || (tempsum == -2));
        // check the three channels if they're legal, and add them if so
        gSign = gPosi = gNega = false;
        int remain = s.size()-i-1;
        if(!nbn && !nbp) { // {-1, 0, 1} channel -> relative origin is -1
          gSign = true;
          int start = tempsum-(-1);
          for(int endsum = 0;endsum <= 2;endsum++) {
            ans += dp[remain][start][endsum]; 
          }
        }
        if(!nbp2 && !nbp) {// {0, 1, 2} channel -> relative origin is 0
          gPosi = true;
          int start = tempsum-0;
          for(int endsum = 0;endsum <= 2;endsum++) {
            ans += dp[remain][start][endsum];
          }
        }
        if(!nbm2 && !nbn) {// {0, -1, -2} channel -> relative origin is -2
          int start = tempsum-(-2);
          for(int endsum = 0;endsum <= 2;endsum++) {
            ans += dp[remain][start][endsum];
          }
          gNega = true;
        }
        ans %= modulo;
        // removing paths we added twice
        if(gSign && gNega) { // exactly one path exists in both gSign and gNega
          ans = (ans - 1 + modulo) % modulo;
        }
        if(gSign && gPosi) {// similarly, only one path exists in both gSign and gPosi
          ans = (ans - 1 + modulo) % modulo;
        }
      }   
    } 

    if(s[i] == 'L') {
      presum++;
    }else {
      presum--;
    }
    if(presum == 2) {
      badMinus2 = badNega =  true;
    } else if(presum == 1) {
      badMinus2 = true;
    } else if(presum == -1) {
      badPlus2 = true;
    } else if(presum == -2) {
      badPlus2 = badPosi = true;
    }
  }
  cout << ans+1;
  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: 0 / 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