QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#610834	#2271. High-Tech Detective	ucup-team4153^#	WA	1ms	3816kb	C++20	2.1kb	2024-10-04 17:39:57	2024-10-04 17:39:59

Judging History

你现在查看的是最新测评结果

[2024-10-04 17:39:59]
评测

测评结果：WA
用时：1ms
内存：3816kb

查看

[2024-10-04 17:39:57]
提交

answer

#include<bits/stdc++.h>
using namespace std;using ld=long double;using ll=long long;
using pll=pair<ll,ll>;using pii=pair<int,int>;
const int M=1e9+7,inv2=(M+1)/2,P=20;const ld eps=1e-8,pi=acos(-1);
ll poww(ll bs,ll x){ll res=1;for(;x;x>>=1,(bs*=bs)%=M)if(x&1)(res*=bs)%=M;return res;}
ll invv(ll bs){return poww(bs,M-2);}
void add(ll&a,ll b){a+=b;if(a>=M)a-=M;}
struct S
{
    int n,mx=0,sp;vector<pii>a;
    void ini()
    {
        cin>>n;string s;map<int,int>mp;
        vector<pii>b(n*2);
        for(auto&[x,y]:b)cin>>s>>x,y=(s[0]=='O'),mp[x]++;
        for(auto&k:b)
        {
            auto[x,y]=k;if(x&&mp[x]==2)continue;
            a.push_back({bool(x),y});
        }
        mp.erase(0);sp=n-mp.size();
    }
    void solve()
    {
        vector<ll>dp(n+2,0);dp[0]=1;//free I_cnt
        for(int i=1,Ic=0;i<=n*2;i++)
        {
            auto [v,sta]=a[i-1];vector<ll>dp2(n+2,0);
            //cout<<v<<'/'<<sta<<'/'<<i<<'\n';
            if(sta==0)//I
            {
                Ic++;
                if(v==1)
                {
                    for(int i=0;i<=Ic;i++)dp2[i]=dp[i];
                }
                else
                {
                    for(int i=1;i<=Ic;i++)dp2[i]=dp[i-1];
                }
            }
            else
            {
                if(Ic==0){cout<<"0\n";return;}
                for(int i=0;i<=Ic;i++)if(i)dp2[i-1]=dp[i]*i%M;
                if(v==0)
                {
                    for(int i=0;i<=Ic;i++)add(dp2[i],dp[i]*(Ic-i)%M);
                }
                Ic--;
            }
            swap(dp,dp2);
            //cout<<Ic<<"|";
            //for(int i=0;i<=n;i++)cout<<dp[i]<<".\n"[i==n];
        }
        ll res=0;for(auto&k:dp)add(res,k);

        for(int i=1;i<=sp;i++)(res*=i)%=M;
        cout<<res<<'\n';
    }
};
signed main()
{
    cout<<fixed<<setprecision(12);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;//cin>>t;
    while(t--){S SS;SS.ini();SS.solve();}
}
/*
1274368 996265816
1807139^
1274369 996265816
1165429^
1274369 996269373
inf^
 */

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3780kb

input:

4
I 1
I 0
O 0
I 0
O 2
I 4
O 0
O 4

output:

result:

ok single line: '3'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

3
I 0
I 0
I 0
O 0
O 0
O 0

output:

result:

ok single line: '36'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

1
I 0
O 1

output:

result:

ok single line: '1'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3528kb

input:

2
I 0
I 1
O 1
O 0

output:

result:

ok single line: '1'

Test #5:

score: 0

Accepted

time: 1ms

memory: 3816kb

input:

4
I 0
I 0
O 0
O 0
I 0
I 3
O 0
O 0

output:

result:

ok single line: '24'

Test #6:

score: 0

Accepted

time: 1ms

memory: 3592kb

input:

8
I 0
I 0
I 0
I 8
I 4
I 0
O 1
I 0
O 8
O 4
I 5
O 0
O 0
O 5
O 0
O 7

output:

result:

ok single line: '576'

Test #7:

score: -100

Wrong Answer

time: 1ms

memory: 3544kb

input:

16
I 5
I 4
I 2
I 1
I 10
I 6
I 14
I 3
I 11
I 7
I 16
O 0
O 7
I 15
O 1
I 8
I 12
O 4
O 11
O 0
I 13
O 14
O 12
O 13
I 0
O 5
O 0
O 0
O 0
O 0
O 0
O 3

output:

result:

wrong answer 1st lines differ - expected: '2400', found: '12000'