QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#195449#2387. Min Max Convertgalen_colin#RE 0ms0kbC++142.9kb2023-10-01 04:26:482023-10-01 04:26:49

Judging History

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

  • [2023-10-01 04:26:49]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-10-01 04:26:48]
  • 提交

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[pr]) ops.push_back({'m', p, pr});
                        else if (a[p] > a[pr]) ops.push_back({'M', p, pr});

                        a[pr] = a[p];

                        p = pr;
                    }

                    ft = l;
                }
                i = p;
                ++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: 0
Runtime Error

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:


result: