QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#296109 | #5072. Future Coder | zyzakioi | WA | 527ms | 3436kb | C++14 | 1.1kb | 2024-01-02 09:53:39 | 2024-01-02 09:53:39 |
Judging History
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 = 1, 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 + 1;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
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: -100
Wrong Answer
time: 527ms
memory: 3436kb
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:
1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 ...
result:
wrong answer 1st numbers differ - expected: '0', found: '1'