QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#682454	#5420. Inscryption	wangcq	WA	218ms	3628kb	C++23	1.8kb	2024-10-27 15:31:34	2024-10-27 15:31:38

Judging History

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

[2024-10-27 15:31:38]
评测

测评结果：WA
用时：218ms
内存：3628kb

查看

[2024-10-27 15:31:34]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-10;
const int N = 100010;
const double PII = acos(-1);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f;
// int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// int dir[8][2] = {{1, 0}, {1, -1}, {1, 1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};
// std::mt19937 rng {std::chrono::steady_clock::now().time_since_epoch().count()};

template <typename T>
void debug(T x) {
    cerr << x << '\n';
}

template <typename T, typename... Args>
void debug(T x, Args... args) {
    cerr << x << ' ';
    debug(args...);
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int s = 1, ok = 0;
    map<int, int> mp;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        mp[a[i]] ++;
        if (a[i] >= 0) s ++;
        else s --;
        if (s <= 0) {
            ok = 1;
        }
    }
    if (ok) {
        cout << -1 << "\n";
        return ;
    }

    auto check = [&](int mid) {
        if (mp[1] + mid >= mp[-1] + mp[0] - mid) {
            return 1;
        } else {
            return 0;
        }
    };
    int l = 0, r = mp[0];
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    int fz = mp[1] + 1 + r;
    int fm = fz - mp[-1] - (mp[0] - r);
    int gcd = __gcd(fz, fm);
    fz /= gcd; fm /= gcd;
    cout << fz << ' ' << fm << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T -- ) {
        solve();
    }
    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3592kb

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:

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 218ms

memory: 3508kb

input:

output:

result:

ok 1000000 lines

Test #3:

score: -100

Wrong Answer

time: 78ms

memory: 3628kb

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:

result:

wrong answer 28th lines differ - expected: '5 4', found: '2 1'