QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#105964#5420. InscryptionRabbieWjy#WA 209ms3532kbC++141.0kb2023-05-16 08:40:152023-05-16 08:40:17

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-16 08:40:17]
  • 评测
  • 测评结果:WA
  • 用时:209ms
  • 内存:3532kb
  • [2023-05-16 08:40:15]
  • 提交

answer

#include <iostream>
#include <cstdio>
using namespace std;

int t,n;
int a[1000010];
int s[1000010],minn[1000010];

int gcd(int x,int y)
{
	while (x ^= y ^= x ^= y %= x);
	return y;
}

int main()
{
	scanf("%d",&t);
	while (t --)
	{
		int A = 1,B = 1;
		bool fl = true;
		scanf("%d",&n);
		for (int i = 1;i <= n;i ++) scanf("%d",a + i);
		minn[n + 1] = s[n + 1] = 0;
		for (int i = n;i >= 1;i --)
			minn[i] = min(minn[i + 1] + a[i],s[i + 1] + a[i]),s[i] = s[i + 1] + a[i];
		int nw = 0;
		for (int i = 1;i <= n;i ++)
		{
//			printf("%d %d %d\n",nw,minn[i],s[i]);
			if (a[i] != 0) nw += a[i];
			else
			{
//				printf("cmp %d %d\n",nw,minn[i]);
				if (minn[i] < 0 && nw > -minn[i]) a[i] = -1,nw --;
				else if (minn[i] >= 0 && nw > 0) a[i] = -1,nw --;
				else a[i] = 1,nw ++;
			}
			if (nw < 0)
			{
				printf("-1\n");
				fl = false;
				break;
			}
		}
		if (!fl) continue;
		for (int i = 1;i <= n;i ++)
			if (a[i] > 0) A ++,B ++;
			else B --;
		int g = gcd(A,B);
		printf("%d %d\n",A / g,B / g);
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3532kb

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: 209ms
memory: 3516kb

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: 107ms
memory: 3512kb

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:

-1
-1
-1
3 2
4 1
-1
-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 2...

result:

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