QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#195311#2387. Min Max Convertgalen_colin#WA 59ms12888kbC++142.8kb2023-10-01 03:19:062023-10-01 03:19:06

Judging History

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

  • [2023-10-01 03:19:06]
  • 评测
  • 测评结果:WA
  • 用时:59ms
  • 内存:12888kb
  • [2023-10-01 03:19:06]
  • 提交

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, i});

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

                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[l];

                        p = pr;
                    }

                    ft = l;
                }
                ++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: 25ms
memory: 8588kb

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: 59ms
memory: 12888kb

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:

171592
M 11908 11909
m 11907 11909
M 11906 11909
M 11905 11909
M 11904 11909
M 11903 11909
m 11902 11909
M 11901 11909
M 11900 11909
M 11899 11909
m 11898 11909
M 11897 11909
M 11896 11909
M 11895 11909
M 11894 11909
M 11893 11909
M 11892 11909
M 11891 11909
M 11890 11909
m 11889 11909
M 11888 11909...

result:

wrong answer Wrong Answer!