#1191489 (C++17) No.1001 注文の多い順列

• 問題: No.1001 注文の多い順列
• ユーザー: vjudge1
• 提出日時: 2026-10-05 10:22:57
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 17 ms / 2,000 ms
• コード長: 3,344 bytes
• コンパイル時間: 704 ms
• コンパイル使用メモリ: 116,376 KB
• 実行使用メモリ: 24,448 KB
• 最終ジャッジ日時: 2026-10-05 10:23:23
• 合計ジャッジ時間: 2,812 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 31

ソースコード

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        debuglen(x);
        debug(args...);
    }
    template <typename T> void debug (T *lt,T *rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    template <typename T> void write (T x) {
        if (x<0) {
            putchar('-');
            x=-x;
        }
        if (x>=10) {
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template <typename T> inline void print (T x) {
        write(x);
        putchar('\n');
    }
    template <typename T> inline void printlen (T x) {
        write(x);
        putchar(' ');
    }
    template <typename T,typename...Args> inline void print (T x,Args...args) {
        printlen(x);
        print(args...);
    }
    template <typename T> inline void print (T *lt,T *rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            if (i==len-1) {
                print(*(lt+i));
                return ;
            }
            printlen(*(lt+i));
        }
    }
}
using namespace io;
const ll N=3e3+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,f[N][N],cnt[2][N];
vector<ll> v[2];
inline void solve () {
    n=read();
    for (ll i=1;i<=n;i++) {
        ll op=read(),x=read();
        v[op].push_back(x);
        cnt[op][x]++;
    }
    for (ll i=1;i<=n;i++) {
        cnt[1][i]+=cnt[1][i-1];
    }
    for (ll i=n;i;i--) {
        cnt[0][i]+=cnt[0][i+1];
    }
    sort(v[0].begin(),v[0].end());
    sort(v[1].begin(),v[1].end());
    f[0][0]=1;
    for (ll i=0;i<n;i++) {
        ll cnt0=cnt[0][i+1],cnt1=cnt[1][i+1];
        for (ll j=0;j<=v[0].size();j++) {
            if (!f[i][j]) {
                continue;
            }
            ll val=cnt0-((ll)v[0].size()-j-1);
            if (j<v[0].size()&&val>0) {
                f[i+1][j+1]+=f[i][j]*val%mod;
                if (f[i+1][j+1]>=mod) {
                    f[i+1][j+1]-=mod;
                }
            }
            val=cnt1-(i-j);
            if (val>0) {
                f[i+1][j]+=f[i][j]*val%mod;
                if (f[i+1][j]>=mod) {
                    f[i+1][j]-=mod;
                }
            }
        }
    }
    print(f[n][v[0].size()]);
}
int main () {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ll T=1;
    while (T--) {
        solve();
    }
    return 0;
}