QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#415680	#6568. Space Alignment	skittles1412^#	AC ✓	0ms	3776kb	C++17	3.3kb	2024-05-21 08:40:07	2024-05-21 08:40:07

Judging History

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

[2024-05-21 08:40:07]
评测

测评结果：AC
用时：0ms
内存：3776kb

查看

[2024-05-21 08:40:07]
提交

answer

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

int det(int a00, int a01, int a10, int a11) {
    return a00 * a11 - a01 * a10;
}

pair<int, int> solve2(const array<int, 3>& e1, const array<int, 3>& e2) {
    auto& [a1, b1, c1] = e1;
    auto& [a2, b2, c2] = e2;
    dbg(a1, b1, c1);
    dbg(a2, b2, c2);

    int cd = det(a1, b1, a2, b2);
    if (!cd) {
        return {-1, -1};
    }

    int cd1 = det(c1, b1, c2, b2), cd2 = det(a1, c1, a2, c2);
    return {cd1 / cd, cd2 / cd};
}

void solve() {
    int n;
    cin >> n;

    // m, a
    vector<array<int, 3>> arr;
    int depth = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        if (s.back() == '}') {
            depth--;
        }

        int cnt_s = 0, cnt_t = 0;
        for (auto& a : s) {
            if (a == 's') {
                cnt_s++;
            } else if (a == 't') {
                cnt_t++;
            }
        }

        arr.push_back({-cnt_t, depth, cnt_s});
        if (s.back() == '{') {
            depth++;
        }
    }

    arr = ({
        vector<array<int, 3>> narr;

        for (auto [cm, ca, cres] : arr) {
            dbg(cm, ca, cres);
            if (!cm && !ca && cres) {
                cout << -1 << endl;
                return;
            } else if (!cm && !ca && !cres) {
                continue;
            }
            int g = gcd(gcd(cm, ca), cres);
            cm /= g;
            ca /= g;
            cres /= g;
            narr.push_back({cm, ca, cres});
        }

        sort(begin(narr), end(narr));
        narr.erase(unique(begin(narr), end(narr)), end(narr));

        narr;
    });

    if (!sz(arr)) {
        cout << 1 << endl;
        return;
    } else if (sz(arr) == 1) {
        auto& [cm, ca, cres] = arr[0];

        if (!ca) {
            if (cres % cm == 0 && cres / cm > 0) {
                cout << cres / cm << endl;
            } else {
                cout << -1 << endl;
            }
        } else {
            auto& [c1, c2, c3] = arr[0];
            for (int m = 1; m <= 10000; m++) {
                long nx = c3 - long(m) * c1;
                if (nx % c2 == 0 && nx / c2 > 0) {
                    cout << m << endl;
                    return;
                }
            }
            cout << -1 << endl;
        }
        return;
    }

    auto [m, a] = solve2(arr[0], arr[1]);
    dbg(m, a);

    for (auto& [cm, ca, cres] : arr) {
        if (cm * m + ca * a != cres) {
            cout << -1 << endl;
            return;
        }
    }

    if (m > 0 && a > 0) {
        cout << m << endl;
    } else {
        cout << -1 << endl;
    }
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3776kb

input:

10
{
ss{
sts{
tt}
t}
t{
ss}
}
{
}

output:

result:

ok single line: '2'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

2
{
}

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3644kb

input:

4
{
ss{
ss}
}

output:

result:

ok single line: '1'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3540kb

input:

4
{
tt{
tt}
}

output:

result:

ok single line: '1'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3564kb

input:

4
{
ss{
s}
}

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3540kb

input:

4
{
tt{
t}
}

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3552kb

input:

4
{
tt{
s}
}

output:

-1

result:

ok single line: '-1'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3628kb

input:

4
{
tt{
sss}
}

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

4
{
tt{
ssss}
}

output:

result:

ok single line: '2'

Test #10:

score: 0

Accepted

time: 0ms

memory: 3540kb

input:

6
{
}
{
tt{
ssss}
}

output:

result:

ok single line: '2'

Test #11:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

100
{
}
{
}
{
t{
ssssssssssssssssssssssssssssssssssss}
t{
t}
t{
tssssssssssssssssssssssssssssssssssss{
tssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss{
tsssssssssssssssssssssssssssssssssssst}
ttssssssssssssssssssssssssssssssssssss{
ssssssssssssssssssssssssssssssssssssssssss...

output:

result:

ok single line: '36'

Test #12:

score: 0

Accepted

time: 0ms

memory: 3576kb

input:

100
{
t{
tssssssssssssssssssss{
ttssssssssssssssssssss{
tsssssssssssssssssssstt{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{
ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...

output:

result:

ok single line: '20'

Test #13:

score: 0

Accepted

time: 0ms

memory: 3468kb

input:

4
{
t{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

result:

ok single line: '999'