QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#613922#5420. Inscryptionucup-team1769#WA 140ms3628kbC++202.7kb2024-10-05 15:04:142024-10-05 15:09:39

Judging History

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

  • [2024-10-05 15:09:39]
  • 评测
  • 测评结果:WA
  • 用时:140ms
  • 内存:3628kb
  • [2024-10-05 15:04:14]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e6;
signed main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int fz = 1, fm = 1, f = 0;
        int ff = 1;
        vector<int> v(n + 1);
        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
        }
        int f0 = -1;
        for (int i = n - 1; i >= 0; i--)
        {
            if (v[i] == 0)
            {
                f0 = i;
                break;
            }
        }
        int fz1 = 0, fm1 = 0;
        int mfm = 0;
        for (int i = f0 + 1; i < n; i++)
        {
            if (v[i] == 1)
            {
                fz1++;
                fm1++;
            }
            else if (v[i] == -1)
            {
                fm1--;
            }
            mfm = min(mfm, fm1);
        }
        mfm *= -1;
        mfm = max(mfm, 0ll);
        for (int i = 0; i <= f0; i++)
        {
            if (!ff)
                continue;
            if (v[i] == 1)
            {
                fz++;
                fm++;
            }
            else if (v[i] == 0)
            {
                f++;
            }
            else if (v[i] == -1)
            {
                if (fm > 1)
                {
                    fm--;
                }
                else
                {
                    if (f > 0)
                    {
                        f--;
                        fz++;
                    }
                    else
                    {
                        ff = 0;
                    }
                }
            }
        }
        if (!ff)
        {
            cout << "-1\n";
        }
        else
        {
            if (f > 0 && fm > mfm + 1)
            {
                int x = min(fm - mfm - 1, f);
                fm -= x;
                f -= x;
            }
            else if (f > 0 && fm < mfm + 1)
            {
                int x = min(mfm + 1 - fm, f);
                fz += x;
                fm += x;
                f -= x;
            }
            if (f > 0)
            {
                int x = (f + 1) / 2;
                fz += x;
                fm += f % 2;
            }

            fz += fz1;
            fm += fm1;
            if (fm < 1)
            {
                cout << "-1\n";
            }
            else
            {
                int _ = gcd(fz, fm);
                cout << fz / _ << " " << fm / _ << endl;
            }
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
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:

3 2
3 1
-1
1 1
2 1
-1

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 140ms
memory: 3604kb

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: 61ms
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:

4 1
-1
-1
3 2
4 1
-1
3 1
-1
3 2
2 1
3 2
-1
-1
2 1
-1
-1
6 1
3 2
3 1
3 2
-1
-1
-1
-1
2 1
5 3
-1
5 4
2 1
-1
3 2
5 1
1 1
4 3
3 2
-1
1 1
-1
2 1
1 1
2 1
1 1
-1
1 1
3 2
-1
2 1
-1
-1
3 2
5 2
1 1
-1
3 1
-1
-1
1 1
-1
6 1
3 2
-1
3 2
4 3
2 1
-1
5 3
3 1
6 1
3 2
2 1
5 4
-1
1 1
-1
3 1
-1
-1
5 3
1 1
2 1
5 2
-1
3 1...

result:

wrong answer 34th lines differ - expected: '-1', found: '4 3'