Submission #555649

#	Time	Username	Problem	Language	Result	Execution time	Memory
555649		600Mihnea	Misspelling (JOI22_misspelling)	C++17	28 / 100	4088 ms	11212 KiB

misspelling

#include <bits/stdc++.h>

bool home = 1;

using namespace std;

typedef long long ll;

const int M = (int) 1e9 + 7;

int add(int a, int b) {
  a += b;
  if (a >= M) {
    return a - M;
  }
  if (a < 0) {
    return a + M;
  }
  return a;
}

int mul(int a, int b) {
  return a * (ll) b % M;
}

int pw(int a, int b) {
  int r = 1;
  while (b) {
    if (b & 1) {
      r = mul(r, a);
    }
    a = mul(a, a);
    b /= 2;
  }
  return r;
}

int dv(int a, int b) {
  return mul(a, pw(b, M - 2));
}

void addup(int &a,int b){
  a=add(a,b);
}

void mulup(int &a,int b){
  a=mul(a,b);
}

struct Interval {
  int l;
  int r;
  int what_first;
};

const int N=(int)5e5+7;
int n,m;
int dp[N][27][2];
Interval dt[N];
int cnt_good;
int vals[N];

void gen(int pos) {
  if(pos>n){
    assert(pos==n+1);
    bool is_ok=1;
    for (int k=1;k<=m;k++){
      int l=dt[k].l,r=dt[k].r;
      int what_is=-1;
      for (int it=l;it<=r;it++){
        if(vals[it]!=vals[it+1]){
          what_is=(vals[it]<vals[it+1]);
          break;
        }
      }
      if(what_is==-1) continue;
      if(what_is!=dt[k].what_first) {
        is_ok=0;
      }
    }
    if(!is_ok) return;
    cout<<++cnt_good<<" : ";
    for (int i=1;i<=n;i++){
      cout<<vals[i]<<" ";
    }
    cout<<"\n";
    return;
  }
  for (int ch=0;ch<26;ch++){
    vals[pos]=ch;
    gen(pos+1);
  }
}

signed main() {
#ifdef ONLINE_JUDGE
  home = 0;
#endif
  home = 0;

  if (home) {
    freopen("I_am_iron_man", "r", stdin);
  }
  else {
    ios::sync_with_stdio(0); cin.tie(0);
  }
  ios::sync_with_stdio(0); cin.tie(0);

  cin>>n>>m;

  for(int i=1;i<=m;i++){
    int l,r;
    cin>>l>>r;
    int what=0;
    if(l>r){
      swap(l,r);
      what=1;
    }
    assert(l<r);
    r--;
    assert(l<=r);
    dt[i]={l, r, what};
  }
  ///gen(1);
  dp[0][26][1]=1;
  for (int i=1;i<=n;i++){
    for (int x=0;x<26;x++) {
      /// compute dp[i][x][??]
      for (int bef=0;bef<=26;bef++){
        if(bef==x) continue;
        for (int j=1;j<=i;j++) {
          int coef=dp[j-1][bef][(x<bef)];
          if(!coef) continue;

          int is_0=0;
          int is_1=0;
          /// go over the restrictions
          for (int k=1;k<=m;k++){
            int l=dt[k].l;
            int r=dt[k].r;
            int what=dt[k].what_first;
            bool inside_i=(l<=i&&i<=r);
            bool inside_j=(l<=j-1&&j-1<=r);
            if(inside_i&&!inside_j){
              assert(what==0||what==1);
              if(what==0) is_0=1;
              if(what==1) is_1=1;
            }
          }
          if(is_0&&is_1) continue;
          if(is_0==0&&is_1==0){
            addup(dp[i][x][0],coef);
            addup(dp[i][x][1],coef);
          }else{
            if(is_0){
              addup(dp[i][x][0],coef);
              assert(is_1==0);
            }
            if(is_1){
              addup(dp[i][x][1],coef);
              assert(is_0==0);
            }
          }
        }
      }
    }
  }
  int sol=0;
  for (int x=0;x<26;x++){
    addup(sol,dp[n][x][0]);
    ///addup(sol,dp[n][x][1]);
  }
  cout<<sol<<"\n";
}
/**
1 x x
y y 3

x 2 x
y y 3
**/

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:102:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11