Submission #1323746

#TimeUsernameProblemLanguageResultExecution timeMemory
1323746qvalentinPizza Party (CCO24_day1problem2)C++20
12 / 12
1129 ms104292 KiB
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<int> A(N), B(N), test(N + 1);
    vector<pair<int, int>> Tab, Tab2;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
        A[i]--;
        test[A[i]]++;
        Tab2.push_back({A[i], i});
    }
    for (int i = 0; i < N; i++)
    {
        cin >> B[i];
        B[i]--;
        test[B[i]]--;
        Tab.push_back({B[i], -i});
    }
    for (int i = 0; i <= N; i++)
    {
        if (test[i] != 0)
        {
            cout << -1 << endl;
            return 0;
        }
    }
    sort(Tab.begin(), Tab.end());
    sort(Tab2.begin(), Tab2.end());
    vector<int> match(N), ans1(N), ans2(N), trans(N);
    for (int i = 0; i < N; i++)
        trans[Tab2[i].second] = i;
    int buff = 0;
    set<int> stacks;
    for (int i = 0; i < N; i++)
    {
        match[i] = -Tab[trans[i]].second;
        auto temp = stacks.lower_bound(match[i]);
        if (temp != stacks.end())
        {
            int pos = *temp;
            ans1[i] = ans2[pos];
            ans2[match[i]] = ans2[pos];
            stacks.erase(pos);
        }
        else
        {
            ans1[i] = buff;
            ans2[match[i]] = buff;
            buff++;
        }
        stacks.insert(match[i]);
    }
    cout << buff << '\n';
    for (int i = 0; i < N - 1; i++)
        cout << ans1[i] + 1 << ' ';
    cout << ans1[N - 1] + 1;
    cout << '\n';
    for (int i = 0; i < N - 1; i++)
        cout << ans2[i] + 1 << ' ';
    cout << ans2[N - 1] + 1;
    cout << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...