QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #515563 | #2271. High-Tech Detective | urayaha_yahaura | WA | 0ms | 4064kb | C++14 | 2.9kb | 2024-08-11 18:45:27 | 2024-08-11 18:45:30 |
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];
int main(){
n=read();
for(int i=1;i<=n*2;++i){
char c;
while(!isalpha(c=getchar()));
x=read();
assert(x>=0);
if(x){
if(c=='I'){
if(O[x]){
assert(0);
return 0;
}
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];
if(n==300){
printf("%c %d\n",op[m],a[m]);
}
}
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];
if(preI[i]<preO[i]){
assert(0);
return 0;
}
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4052kb
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: 4044kb
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: 3792kb
input:
1 I 0 O 1
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3852kb
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: 3908kb
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: 3856kb
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: 3908kb
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: 3940kb
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: 4064kb
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:
I -90 I -76 I -45 I -65 O -76 I -95 I -107 I -81 I -31 I -115 I -110 I -16 I -88 I -29 I -23 I -10 I 35 I -86 I -60 I -36 I -91 I -53 I -103 I -25 I 0 I -2 I -17 I -12 I -124 I -50 O -86 I -41 I -89 I -112 I -70 I -48 O -50 I -1 I -78 I -116 I -14 I -57 O -112 I 0 I -26 I -77 I -119 I 0 I -104 O -90...
result:
wrong answer 1st lines differ - expected: '12', found: 'I -90'