Submission #555662

#	Time	Username	Problem	Language	Result	Execution time	Memory
555662		600Mihnea	Misspelling (JOI22_misspelling)	C++17	8 / 100	4099 ms	6988 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][30][2];
int transfer[N][30];
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);
  }
}

void compute_row(int i){
  int cur=0;
  for (int x=0;x<27;x++){
    addup(cur,dp[i][x][0]);
    addup(transfer[i][x+1],cur);
  }
  cur=0;
  for(int x=27;x>=1;x--){
    addup(cur,dp[i][x][1]);
    addup(transfer[i][x-1],cur);
  }
}

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;
  compute_row(0);
  for (int i=1;i<=n;i++){
    vector<int> inds;
    int m0=0,m1=0;
    for (int k=1;k<=m;k++){
      int l=dt[k].l;
      int r=dt[k].r;
      int what=dt[k].what_first;
      if(l<=i&&i<=r){
        inds.push_back(k);
        if(what==0) m0=max(m0,l);
        if(what==1) m1=max(m1,l);
      }
    }
    for (int x=0;x<26;x++) {
      /// compute dp[i][x][??]
      for (int j=1;j<=i;j++) {
        int is_0=0;
        int is_1=0;
        /// go over the restrictions
        for (auto &k:inds){

          int l=dt[k].l;
          int r=dt[k].r;
          int what=dt[k].what_first;
          bool inside_j=(l<=j-1&&j-1<=r);
          if(l>j-1){
            if(what==0) is_0=1;
            if(what==1) is_1=1;
          }
        }
        assert(is_0==(m0>j-1));
        assert(is_1==(m1>j-1));
        if(is_0&&is_1) continue;
        int coef=transfer[j-1][x];

        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);
          }
        }
      }
    }
    compute_row(i);
  }
  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:165:16: warning: unused variable 'inside_j' [-Wunused-variable]
  165 |           bool inside_j=(l<=j-1&&j-1<=r);
      |                ^~~~~~~~
misspelling.cpp:116:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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