The 2022 ICPC Asia Nanjing Regional Contest (G. Inscryption)

Problem - G - Codeforces

反悔贪心

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"

const int N = 1e6 + 5;

inline int gcd(int a, int b) {
    return b > 0 ? gcd(b, a % b) : a;
}

int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T = 1; cin >> T;
    while(T--){
        int n; cin >> n;
        //sum -> 所有元素和
        //tot -> 所有元素数量
        //op  -> 选了几个0变成-1
        int sum = 1, tot = 1, op = 0;
        bool ok = true;
        for(int i = 1; i <= n; i++){
            int x; cin >> x;
            if(x == 1){
                sum++; tot++;
            }else if(x == -1){
                if(tot > 1) tot--;
                else {
                    if(op) op--, sum++, tot++;
                    else ok = false;
                }
            }else{
                if(tot > 1) tot--, op++;
                else tot++, sum++; 
            }
        }
        if(!ok) cout << -1 << endl;
        else {
            cout << sum / gcd(sum, tot) << ' ' << tot / gcd(sum, tot) << endl;
        }
    }
    return 0;    
}