Submission #1163337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163337		Zero_OP	Misspelling (JOI22_misspelling)	C++20	8 / 100	4094 ms	21832 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;

using vpi = vector<pi>;
using vpl = vector<pl>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAX = 5e5 + 5;

const int mod = 1e9 + 7;

struct mint{
      int v;
      mint(int v = 0) : v(v) {}

      friend bool operator == (const mint& a, const mint& b){ return a.v == b.v; }
      friend bool operator != (const mint& a, const mint& b){ return a.v != b.v; }

      mint& operator += (const mint& o){ v += o.v; if(v >= mod) v -= mod; return *this; }
      mint& operator -= (const mint& o){ v -= o.v; if(v < 0) v += mod; return *this; }
      mint& operator *= (const mint& o){ v = 1LL * v * o.v % mod; return *this; }

      friend mint operator + (mint a, const mint& b){ return a += b; }
      friend mint operator - (mint a, const mint& b){ return a -= b; }
      friend mint operator * (mint a, const mint& b){ return a *= b; }

      friend ostream& operator << (ostream& out, const mint& o){ return out << o.v; }
};

int N, M, sign[MAX], positive_require[MAX], negative_require[MAX];
mint dp[2][26], ans;

void construct(){
      FOR(i, 0, 26) dp[0][i] = 1;

//      FOR(i, 1, N) cout << sign[i] << ' '; cout << '\n';
      int cur = 0, pre = 1;
      FOR(i, 1, N){
            if(sign[i] != 0){
                  swap(cur, pre);
                  if(sign[i] == -1){
                        mint sum = 0;
                        ROF(j, 26, 0){
                              dp[cur][j] = sum;
                              sum += dp[pre][j];
                        }
                  } else{
                        mint sum = 0;
                        FOR(j, 0, 26){
                              dp[cur][j] = sum;
                              sum += dp[pre][j];
                        }
                  }

//                  FOR(j, 0, 26) cout << dp[cur][j] << ' '; cout << '\n';
            }
      }

//      mint tmp = 0;
//      FOR(i, 0, 26) tmp += dp[cur][i];
//      cout << dbg(tmp) << '\n';
      FOR(i, 0, 26) ans += dp[cur][i];
}

void rec(int pos){
      if(pos == N){
            bool ok = true;
            FOR(i, 1, N){
                  if(positive_require[i]){
                        FOR(j, i, positive_require[i]+1){
                              if(sign[j] != 0){
                                    if(sign[j] == -1){
                                          ok = false;
                                    }
                                    break;
                              }
                        }
                        if(!ok) break;
                  }

                  if(negative_require[i]){
                        FOR(j, i, negative_require[i]+1){
                              if(sign[j] != 0){
                                    if(sign[j] == +1){
                                          ok = false;
                                    }
                                    break;
                              }
                        }
                        if(!ok) break;
                  }
            }

            if(ok) construct();
      } else{
            sign[pos] = -1;
            rec(pos+1);
            sign[pos] = 0;
            rec(pos+1);
            sign[pos] = +1;
            rec(pos+1);
      }
}

int main(){
      ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL

      cin >> N >> M;
      while(M--){
            int a, b;
            cin >> a >> b;
            if(a < b){
                  maximize(positive_require[a], b-1);
            } else{
                  maximize(negative_require[b], a-1);
            }
      }

      rec(1);
      cout << ans.v << '\n';



      return 0;
}

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