제출 #555651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555651		600Mihnea	Misspelling (JOI22_misspelling)	C++17	8 / 100	4075 ms	6196 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];
int pref[N][27];
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 j=1;j<=i;j++) {
        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;
        int coef=0;
        for (int bef=0;bef<x;bef++) addup(coef,dp[j-1][bef][0]);
        for (int bef=x+1;bef<=26;bef++) addup(coef,dp[j-1][bef][1]);

        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
**/

컴파일 시 표준 에러 (stderr) 메시지

misspelling.cpp: In function 'int main()':
misspelling.cpp:103:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     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