QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#195873#2387. Min Max Convertgalen_colinWA 20ms10104kbC++142.9kb2023-10-01 08:46:442023-10-01 08:46:44

Judging History

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

  • [2023-10-01 08:46:44]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:10104kb
  • [2023-10-01 08:46:44]
  • 提交

answer

// comp = compile
// compr = compile & run
// in terminal, gocp goes to cp directory

#include <bits/stdc++.h>
using namespace std;

#include <bits/extc++.h>
using namespace __gnu_pbds;
using ll = long long;

using ordered_set = tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>;
using pl = pair<ll, ll>;
#define f first
#define s second

ll n;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    vector<ll> a(n), b(n);
    for (ll &x: a) cin >> x;
    for (ll &x: b) cin >> x;

    vector<ll> nxt(n);
    for (ll i = n - 1; i >= 0; i--){ 
        if (i == n - 1 || b[i] != b[i + 1]) nxt[i] = i + 1;
        else nxt[i] = nxt[i + 1];
    }

    ll pt = -1, last = -1;

    vector<array<ll, 3>> ops;

    for (ll i = 0; i < n; i++) {
        if (last == b[i]) {
            if (pt < i) {
                ll r = i;

                vector<pl> op;
                op.push_back({i - 1, nxt[i] - 1});

                ll lb = nxt[i];
                for (ll j = i; j <= r; j++) {
                    if (lb < n && a[j] == b[lb]) {
                        op.push_back({j, nxt[lb] - 1});
                        r = lb;
                        lb = nxt[lb];
                    }
                }

                ll p = op.back().s;

                ll ft = op.back().s + 1;
                while (op.size()) {
                    pl x = op.back();
                    op.pop_back();
                    ll l = x.f, r = x.s;

                    // cout << l << " " << r << '\n';

                    for (ll p = l; p < r;) {
                        ll pr = p + 1;
                        if (p + 1 >= ft) pr = r;

                        if (a[p] < a[p + 1]) ops.push_back({'m', p, pr});
                        else if (a[p] > a[p + 1]) ops.push_back({'M', p, pr});

                        a[pr] = a[p];

                        p = pr;
                    }

                    ft = l;
                }
                i = p;
                pt = i;
                last = a[pt];
            }
            continue;
        }

        if (pt < i) {
            assert(pt == i - 1);
            last = a[i];
            ++pt;
        }
        ll pr = pt;
        while (pt < n && a[pt] != b[i]) ++pt;

        if (pt == n) {
            cout << -1 << '\n';
            return 0;
        }

        for (ll t = pt; t - 1 > pr; t--) {
            if (a[t - 1] < a[pt]) ops.push_back({'M', t - 1, pt});
            else if (a[t - 1] > a[pt]) ops.push_back({'m', t - 1, pt});
        }

        if (last < a[pt]) ops.push_back({'M', i, pt});
        else if (last > a[pt]) ops.push_back({'m', i, pt});

        last = a[pt];
    }

    assert(ops.size() <= 2 * n);

    cout << ops.size() << '\n';
    for (auto x: ops) {
        cout << ((char)x[0]) << " " << x[1] + 1 << " " << x[2] + 1 << '\n';
    }
}

详细

Test #1:

score: 100
Accepted
time: 20ms
memory: 10104kb

input:

100000
80159 24037 50544 49029 20937 95595 93373 58274 55943 97218 6019 21069 7470 92698 25184 8879 68760 75476 81465 87494 92468 11304 66134 85457 88083 59682 95187 18518 63052 61310 69855 4557 82231 40498 38847 95156 2291 94195 90442 94252 27042 63660 32300 25128 47881 8924 61749 44499 7315 93110 ...

output:

99996
m 8557 8558
M 8556 8558
M 8555 8558
M 8554 8558
m 8553 8558
M 8552 8558
m 8551 8558
M 8550 8558
M 8549 8558
m 8548 8558
m 8547 8558
m 8546 8558
m 8545 8558
M 8544 8558
M 8543 8558
m 8542 8558
M 8541 8558
M 8540 8558
M 8539 8558
M 8538 8558
M 8537 8558
m 8536 8558
m 8535 8558
M 8534 8558
m 8533...

result:

ok Ok!

Test #2:

score: -100
Wrong Answer
time: 12ms
memory: 7280kb

input:

100000
52110 54961 56556 66397 51669 14806 41661 88458 26640 46803 72143 75555 19367 69221 29619 75969 50803 80447 95452 28192 27682 39097 33475 17889 85701 1837 72563 72122 77651 21691 81387 96195 50326 76820 69185 36073 45307 53185 99323 50653 28532 62587 82103 23443 70343 56290 32050 64725 92174 ...

output:

-1

result:

wrong answer Wrong Answer!