QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#106477 | #5420. Inscryption | wsygxlj | WA | 222ms | 3760kb | C++14 | 1.4kb | 2023-05-17 21:13:47 | 2023-05-17 21:13:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int c1[1000006],c2[1000005],a[1000005],cs[1000006];
int main()
{
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
c1[i]=c2[i]=0,cs[i]=0;
}
c1[n+1]=c2[n+1]=0;
for(int i=n;i>0;i--)
{
if(a[i]==1)
{
c2[i]=c2[i+1];c1[i]=c1[i+1]+1;
}
else {
c2[i]=c2[i+1]+1;c1[i]=c1[i+1];
}
}
int css=0;
for(int i=n;i>0;i--)
{
if(a[i]==-1) css++;
else if(a[i]==1) css--;
else cs[i]=css;
}
int f=1;
long long c=1,b=1;
for(int i=1;i<=n;i++)
{
//cout<<c<<" "<<b<<" "<<c1[i]<<" "<<c2[i]<<endl;
if(a[i]==1) c++,b++;
else if(a[i]==-1)
{
if(b>=2) b--;
else
{
f=0;break;
}
}
else
{
if(b+c1[i]>=c2[i]+1&&b>=2&&b>cs[i]) b--;
else c++,b++;
}
}
if(f)
{
long long g=__gcd(c,b);
printf("%lld %lld\n",c/g,b/g);
}
else printf("-1\n");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3520kb
input:
6 7 1 1 1 -1 1 1 -1 4 1 0 -1 0 4 0 -1 -1 0 1 0 2 0 0 1 -1
output:
3 2 3 1 -1 1 1 2 1 -1
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 222ms
memory: 3564kb
input:
1000000 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 -1 1 0 1 0 1 1 1 0 1 -1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 -1 1 1 1 1 1 -1 1 0 1 1 1 0 1 -1 1 0 1 -1 1 1 1 -1 1 0 1 1 1 1 1 -1 1 0 1 -1 1 -1 1 -1 1 -1 1 0 1 0 1 -1 1 0 1 -1 1 0 1 0 1 0 1 0 1 0 1 -1 1 1 1 0 1 0 1 1 1 0 1 -1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 ...
output:
1 1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 -1 -1 -1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 ...
result:
ok 1000000 lines
Test #3:
score: -100
Wrong Answer
time: 118ms
memory: 3760kb
input:
181249 6 1 0 -1 0 1 0 4 1 -1 -1 -1 8 -1 0 0 0 1 -1 1 1 3 0 1 0 6 1 0 -1 1 -1 0 4 1 -1 -1 -1 9 0 1 0 -1 -1 0 -1 0 1 1 -1 3 0 -1 1 5 0 0 1 -1 1 3 1 -1 0 6 -1 0 0 -1 0 1 8 1 -1 -1 -1 0 1 -1 0 2 0 0 3 -1 1 0 3 0 -1 -1 10 0 1 0 -1 1 1 0 -1 1 0 3 1 0 0 9 1 -1 1 -1 0 -1 0 0 0 3 0 1 0 3 -1 0 0 7 -1 0 -1 -1 ...
output:
4 1 -1 -1 3 2 4 1 -1 3 1 -1 3 2 2 1 3 2 -1 -1 2 1 -1 -1 6 1 3 2 3 1 3 2 -1 -1 -1 -1 2 1 5 3 -1 5 4 2 1 -1 3 2 5 1 1 1 -1 3 2 -1 1 1 -1 2 1 1 1 -1 1 1 -1 1 1 3 2 -1 -1 -1 -1 3 2 5 2 1 1 -1 3 1 -1 -1 1 1 -1 6 1 3 2 -1 3 2 4 3 2 1 -1 5 3 3 1 6 1 -1 2 1 -1 -1 1 1 -1 3 1 -1 -1 -1 1 1 2 1 5 2 -1 3 1 4 3 3...
result:
wrong answer 71st lines differ - expected: '5 4', found: '-1'