QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#296113#5072. Future CoderzyzakioiWA 519ms3440kbC++141.1kb2024-01-02 09:57:172024-01-02 09:57:17

Judging History

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

  • [2024-01-02 09:57:17]
  • 评测
  • 测评结果:WA
  • 用时:519ms
  • 内存:3440kb
  • [2024-01-02 09:57:17]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int t, n, a;
vector<int>pos, neg;
int get1(int now) {
	int l = 0, r = pos.size() - 1, mid, ans = pos.size();
	while (l <= r) {
		mid = (l + r) >> 1;
		if (pos[mid] * now < pos[mid] + now) {
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	return pos.size() - ans;
}
int get2(int s, int e, int now) {
	int l = s, r = e, mid, ans = s;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (pos[mid] * now < pos[mid] + now) {
			ans = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	return ans - s;
}
signed main() {
	cin >> t;
	while (t--) {
		cin >> n;
		pos.clear();
		neg.clear();
		for (int i = 1; i <= n; ++i) {
			cin >> a;
			if (a >= 0)
				pos.push_back(a);
			else
				neg.push_back(a);
		}
		sort(pos.begin(), pos.end());
		sort(neg.begin(), neg.end());
		long long ans = 0;
		for (auto i : neg)
			ans += get1(i);
		for (int i = 0; i < pos.size(); ++i)
			ans += get2(i, pos.size() - 1, pos[i]);
		cout << ans << endl;
	}
	return 0;
}

詳細信息

Test #1:

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

input:

2
8
3 -1 4 1 -5 9 2 -6
1
0

output:

19
0

result:

ok 2 number(s): "19 0"

Test #2:

score: 0
Accepted
time: 519ms
memory: 3440kb

input:

1000000
1
-164353707
1
-282757533
1
916961328
1
-540297420
1
866372576
1
1
1
871062154
1
873753814
1
1
1
1
1
636976909
1
789718633
1
200630859
1
-855838121
1
1
1
1
1
282306491
1
-308064257
1
-220028474
1
396002423
1
765070684
1
407981535
1
1
1
184126913
1
935672434
1
-70908999
1
1
1
669665925
1
1
1
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000000 numbers

Test #3:

score: -100
Wrong Answer
time: 363ms
memory: 3436kb

input:

500000
2
1 790170188
2
-886864567 1
2
-579023597 746881890
2
-534254391 -756978339
2
1 1
2
-617821991 -444756587
2
-676343428 -276446748
2
-422136307 1
2
1 1
2
-280282708 -901772076
2
-958271412 676715004
2
157313986 920829551
2
1 1
2
-796480068 1
2
1 1
2
616588559 1
2
1 -922399591
2
620860427 1
2
-...

output:

1
1
1
0
1
0
0
1
1
0
0
1
1
1
1
1
1
1
0
1
1
0
1
1
0
1
1
0
1
1
1
0
0
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
1
0
1
1
1
1
1
1
1
1
0
1
0
1
0
1
1
0
1
1
1
1
0
1
0
1
0
1
1
0
1
0
1
1
1
1
1
1
0
1
0
1
0
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
0
1
1
1
1
1
1
1
0
1
0
1
1
0
1
1
1
1
1
1
1
1
0
1
0
0
0
1
1
1
0
...

result:

wrong answer 11th numbers differ - expected: '1', found: '0'