QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#875620#8805. Pizza PartyMispertion#0 925ms724352kbC++232.4kb2025-01-30 00:01:282025-01-30 00:01:28

Judging History

This is the latest submission verdict.

  • [2025-01-30 00:01:28]
  • Judged
  • Verdict: 0
  • Time: 925ms
  • Memory: 724352kb
  • [2025-01-30 00:01:28]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
#define int ll
using ld = long double;
using pii = pair<int, int>;

#define S second
#define F first
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define mispertion ios_base::sync_with_stdio(0),cin.tie(0)
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()

const ld PI = 3.1415926535;
const ld eps = 1e-9;
const int N = 1e6 + 2;
const int M = 1.5e6 + 13;
ll mod = 1e9+7;
const int infi = 1e18;
const ll infl = 1e16;
const int P = 31;

int mult(int a, int b) {
    return a * 1LL * b % mod; }

int sum(int a, int b) {
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}

ll binpow(ll a, ll n) {
    if (n == 0) return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % (mod);
    } else {
        ll b = binpow(a, n / 2);
        return b * b % (mod);
    }
}

int n, a[N], b[N], used[N], ans[N], cur = 0, lst[N], pl[N];
stack<int> st[N];

inline void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= n; i++){
        if(used[b[i]]){
            cout << -1 << '\n';
            return;
        }
        used[b[i]] = i;
    }
    reverse(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        int bl = -1;
        for(int j = 1; j <= cur; j++){
            if(used[a[i]] > lst[j]){
                if(bl == -1 || lst[bl] < lst[j])
                    bl = j;
            }
        }
        if(bl == -1){
            cur++;
            ans[i] = cur;
            pl[used[a[i]]] = cur;
            lst[cur] = used[a[i]];
        }else{
            ans[i] = bl;
            pl[used[a[i]]] = bl;
            lst[bl] = used[a[i]];
        }
    }
    cout << cur << '\n';
    for(int i = n; i >= 1; i--){
        cout << ans[i] << ' ';
        st[ans[i]].push(a[i]);
    }
    cout << '\n';
    for(int i = 1; i <= n; i++){
        cout << pl[i] << ' ';
        assert(st[pl[i]].size() > 0 && st[pl[i]].top() == b[i]);
        st[pl[i]].pop();
    }
    cout << '\n';
}

signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i ++){
        solve();
    }
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 168ms
memory: 693832kb

input:

1000000
1 1 1 2 1 1 1 1 1 2 1 1 1 2 1 2 1 1 1 2 2 1 2 1 2 2 2 2 2 1 2 2 1 1 1 2 1 1 2 1 2 2 2 2 2 2 2 1 2 1 2 2 1 1 2 1 2 2 2 1 1 2 2 1 1 1 1 2 1 2 2 1 2 2 2 1 2 1 1 2 1 1 1 2 1 2 2 1 1 1 2 2 2 2 1 2 1 1 1 2 2 2 1 1 1 1 1 2 2 2 1 1 1 2 2 2 2 1 2 2 2 1 2 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 1 2 1 1 2 1 ...

output:

-1

result:

wrong answer jury uses fewer stacks: jans = 2, pans = 1061109567

Subtask #2:

score: 0
Wrong Answer

Test #24:

score: 0
Wrong Answer
time: 114ms
memory: 685020kb

input:

5000
3140 3541 3540 3884 2792 3966 1359 549 2273 2669 2100 4448 4722 3937 23 3964 4910 3490 61 2723 2554 4177 3025 4909 2127 939 2536 835 2801 459 3374 972 4687 2102 2919 4367 4905 3414 869 2272 507 4210 2906 2584 1639 2020 3287 3447 2500 4866 3284 2010 1826 331 1873 3895 4946 889 3059 894 4233 2541...

output:

134
36 119 13 115 123 42 83 99 90 85 134 79 89 123 81 59 77 91 107 114 118 79 71 30 84 13 133 80 23 122 68 99 121 132 43 120 75 88 122 80 132 131 78 74 113 121 99 22 98 62 76 82 72 58 21 129 52 86 79 103 132 117 96 108 88 124 81 45 72 121 78 57 74 120 71 80 52 42 90 57 31 82 133 130 120 118 95 32 42...

result:

wrong output format Expected EOLN

Subtask #3:

score: 0
Wrong Answer

Test #39:

score: 0
Wrong Answer
time: 925ms
memory: 724352kb

input:

1000000
134990 280863 995875 82485 490673 517020 49269 636214 69331 626226 96180 743288 524606 324456 937362 164072 680663 931183 195920 618400 741187 164410 478750 590824 160168 192530 154228 661164 17160 343556 653139 229351 350929 719054 634472 433811 352199 163260 833268 56711 963125 346135 9350...

output:

1996
1943 1769 630 1622 1703 727 1579 1617 1497 1425 1288 489 1324 1922 1365 574 1287 1309 1996 373 1503 1305 1488 1601 1475 1488 1421 1422 1911 1861 1105 1712 993 1928 1593 1495 1777 972 1774 971 1731 1137 1636 1151 1397 1674 1319 342 691 1287 904 1450 1639 1821 1847 519 1269 1045 1857 786 1341 822...

result:

wrong output format Expected EOLN