QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #515468 | #2271. High-Tech Detective | urayaha_yahaura# | WA | 0ms | 4056kb | C++14 | 2.6kb | 2024-08-11 17:56:57 | 2024-08-11 17:56:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+7;
const int mod=1e9+7;
int read(){
int x=0;
char c;
while(!isdigit(c=getchar()));
while(isdigit(c)){
x=x*10+(c^48);
c=getchar();
}
return x;
}
struct mint{
int x;
mint(int x=0):x(x%mod){}
friend mint operator +(mint a,mint b){
a.x+=b.x;
if(a.x>=mod)
a.x-=mod;
return a;
}
friend mint operator *(mint a,mint b){
return mint(1ll*a.x*b.x%mod);
}
};
int qpow(int a,int x){
mint A=a,res=1;
while(x){
if(x&1)
res=res*A;
A=A*A;
x>>=1;
}
return res.x;
}
int n,m,x,cnt,I[N],O[N];
char op[N],a[N];
int preI[N],preO[N],sufI[N],sufO[N],isufO[N];
mint f[N],g[N];
signed main(){
n=read();
for(int i=1;i<=n*2;++i){
char c;
while(!isalpha(c=getchar()));
x=read();
if(x){
if(c=='I')
I[x]=i;
else{
if(!I[x])
++cnt;
O[x]=i;
}
}
op[i]=c;
a[i]=x;
}
for(int i=1;i<=n*2;++i){
if(I[a[i]]&&O[a[i]])
continue;
++m;
op[m]=op[i];
a[m]=a[i];
}
for(int i=1;i<=m;++i){
preI[i]=preI[i-1];
preO[i]=preO[i-1];
if(op[i]=='O')
++preO[i];
else
++preI[i];
}
for(int i=m;i;--i){
sufI[i]=sufI[i+1];
sufO[i]=sufO[i+1];
if(op[i]=='O'&&a[i])
++sufO[i];
else if(op[i]=='I'&&!a[i])
++sufI[i];
isufO[i]=qpow(sufO[i],mod-2);
}
f[cnt]=1;
for(int i=1;i<=m;++i){
for(int j=0;j<=cnt;++j){
if(sufI[i]<j){
g[j]=0;
continue;
}
if(op[i]=='I'){
if(a[i])
g[j]=f[j];
else
g[j]=f[j+1]*(j+1)+f[j]*(sufI[i]-j);
}
else{
if(a[i]){
if(sufO[i]>j)
g[j]=f[j]*(sufO[i]-j)*isufO[i];
else
g[j]=0;
}
else{
if(preI[i-1]-preO[i-1]>sufO[i]-j)
g[j]=f[j]*(preI[i-1]-preO[i-1]-sufO[i]+j);
else
g[j]=0;
}
}
}
for(int j=0;j<=cnt;++j)
f[j]=g[j];
}
printf("%d\n",f[0].x);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3916kb
input:
4 I 1 I 0 O 0 I 0 O 2 I 4 O 0 O 4
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4048kb
input:
3 I 0 I 0 I 0 O 0 O 0 O 0
output:
36
result:
ok single line: '36'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
1 I 0 O 1
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
2 I 0 I 1 O 1 O 0
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
4 I 0 I 0 O 0 O 0 I 0 I 3 O 0 O 0
output:
24
result:
ok single line: '24'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4056kb
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:
576
result:
ok single line: '576'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3860kb
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:
2400
result:
ok single line: '2400'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
50 I 42 I 32 I 29 I 14 I 27 I 0 I 9 I 18 I 11 I 25 O 31 I 39 I 41 I 23 I 43 I 1 I 35 O 25 I 44 I 5 I 28 I 48 I 33 I 50 I 21 I 19 O 29 O 33 O 19 O 44 I 17 I 6 O 32 O 23 I 30 O 42 I 13 O 27 I 20 I 34 I 15 O 17 O 30 I 36 O 0 I 0 I 10 O 21 O 36 I 40 O 34 O 9 I 4 O 20 O 14 I 47 O 1 I 22 O 50 I 26 I 24 I ...
output:
2
result:
ok single line: '2'
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3872kb
input:
300 I 117 I 122 I 64 I 166 I 65 I 70 I 81 I 180 I 270 I 211 I 191 I 95 I 103 I 271 O 180 I 161 I 108 I 149 I 175 I 79 I 225 I 141 I 146 I 240 I 168 I 227 I 233 I 75 I 286 I 7 I 43 I 246 I 285 I 63 I 73 I 282 I 269 I 36 I 291 I 2 I 55 I 41 O 73 I 170 I 25 I 196 I 220 I 33 I 165 I 203 O 70 I 153 I 289...
output:
0
result:
wrong answer 1st lines differ - expected: '12', found: '0'