QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#666651 | #5420. Inscryption | XiaoretaW | WA | 171ms | 3632kb | C++20 | 1.8kb | 2024-10-22 19:29:40 | 2024-10-22 19:29:47 |
Judging History
answer
#include <bits/stdc++.h>
#define debug(...) 42;
#ifdef LOCAL
#include "debug.h"
#endif
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a - 1; i >= b; --i)
template<typename T> bool setmin(T &a, T b) { return (a > b ? a = b, 1 : 0); }
template<typename T> bool setmax(T &a, T b) { return (a < b ? a = b, 1 : 0); }
#define vi vector<int>
#define vl vector<ll>
#define trav(it, a) for(auto& it: a)
void solve(){
int n; cin >> n;
vi a(n); trav(ai, a) cin >> ai;
int tot = count(all(a), 0);
auto ck = [&](int cnt)->pair<bool, pii>{
auto b = a;
int up = 1, down = 1;
cnt = tot - cnt;
rep(i,0,n){
if(a[i] == 0){
a[i] = (cnt ? 1 : -1);
cnt -= 1;
}
if(a[i] == 1){
up += 1;
down += 1;
}else{
assert(a[i] == -1);
down -= 1;
}
if(down <= 0){
a = b;
return{false, {-1, -1}};
}
}
a = b;
int g = gcd(up, down);
return {true, {up / g, down / g}};
};
int lo = 0, hi = tot;
while(lo < hi){
int mid = (lo + hi + 1) >> 1;
if(ck(mid).fi) lo = mid;
else hi = mid-1;
}
auto res = ck(lo);
if(res.fi){
cout << res.se.fi << ' ' << res.se.se << '\n';
}else{
cout << -1 << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int T; cin >> T;
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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: 171ms
memory: 3632kb
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: 86ms
memory: 3560kb
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:
5 3 -1 -1 3 2 4 1 -1 3 1 -1 3 2 2 1 3 2 -1 -1 2 1 -1 -1 8 5 3 2 3 1 3 2 -1 -1 -1 -1 2 1 5 3 -1 5 4 2 1 -1 3 2 2 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 3 2 1 1 -1 3 1 -1 -1 1 1 -1 7 3 3 2 -1 3 2 4 3 2 1 -1 5 3 3 1 6 1 -1 2 1 5 4 -1 1 1 -1 3 1 -1 -1 5 3 1 1 2 1 5 2 -1 3 1 4 3...
result:
wrong answer 1st lines differ - expected: '4 1', found: '5 3'