oj.uz

Submission #1055778

# Submission time Handle Problem Language Result Execution time Memory
1055778 2024-08-13T05:15:06 Z 정희우(#11069) Pizza Party (CCO24_day1problem2) C++17
12 / 12
 490 ms 84664 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_N=1000010;

int n;
int a[MAX_N],b[MAX_N];
int cnt[MAX_N];
int col[MAX_N][3];
set<pii> st;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    int mx=0;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
        mx=max(mx,a[i]);
        col[a[i]][0]=i;
    }
    for(int i=0;i<n;i++)
    {
        cin >> b[i];
        cnt[b[i]]--;
        col[b[i]][1]=i;
    }
    for(int i=1;i<=n;i++)
        if(cnt[i]!=0)
        {
            cout << -1;
            return 0;
        }
    if(mx<=2)
    {
        int flag=1;
        for(int i=0;i<n;i++)
            if(a[i]!=b[n-1-i])flag=0;
        if(flag)
        {
            cout << "1\n";
            for(int t=0;t<2;t++,cout << '\n')
            for(int i=0;i<n;i++)
            {
                cout << '1';
                if(i<n-1)cout << ' ';
            }
        }
        else
        {
            cout << "2\n";
            for(int i=0;i<n;i++)
            {
                cout << a[i];
                if(i<n-1)cout << ' ';
            }
            cout << '\n';
            for(int i=0;i<n;i++)
            {
                cout << b[i];
                if(i<n-1)cout << ' ';
            }
        }
        return 0;
    }
    int k=0;
    for(int i=0;i<n;i++)
    {
        int o=col[a[i]][1];
        auto it=st.lower_bound({o,0});
        if(it==st.end())
            col[a[i]][2]=++k;
        else
        {
            col[a[i]][2]=it->second;
            st.erase(it);
        }
        st.insert({o,col[a[i]][2]});
    }
    cout << k << '\n';
    for(int i=0;i<n;i++)
    {
        cout << col[a[i]][2];
        if(i<n-1)cout << ' ';
    }
    cout << '\n';
    for(int i=0;i<n;i++)
    {
        cout << col[b[i]][2];
        if(i<n-1)cout << ' ';
    }
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 12256 KB good job!
2 Correct 143 ms 12084 KB good job!
3 Correct 123 ms 12300 KB good job!
4 Correct 140 ms 12116 KB good job!
5 Correct 125 ms 12116 KB good job!
6 Correct 128 ms 12116 KB good job!
7 Correct 125 ms 12068 KB good job!
8 Correct 127 ms 12116 KB good job!
9 Correct 131 ms 12372 KB good job!
10 Correct 124 ms 12112 KB good job!
11 Correct 123 ms 12112 KB good job!
12 Correct 131 ms 12520 KB good job!
13 Correct 0 ms 344 KB good job!
14 Correct 0 ms 348 KB good job!
15 Correct 0 ms 348 KB good job!
16 Correct 54 ms 8040 KB good job!
17 Correct 54 ms 8272 KB good job!
18 Correct 54 ms 8276 KB good job!
19 Correct 53 ms 8272 KB good job!
20 Correct 53 ms 8272 KB good job!
21 Correct 62 ms 8212 KB good job!
22 Correct 125 ms 12152 KB good job!
23 Correct 0 ms 348 KB good job!

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB good job!
2 Correct 0 ms 604 KB good job!
3 Correct 1 ms 604 KB good job!
4 Correct 1 ms 604 KB good job!
5 Correct 1 ms 604 KB good job!
6 Correct 1 ms 604 KB good job!
7 Correct 1 ms 604 KB good job!
8 Correct 1 ms 604 KB good job!
9 Correct 2 ms 604 KB good job!
10 Correct 1 ms 604 KB good job!
11 Correct 2 ms 860 KB good job!
12 Correct 1 ms 604 KB good job!
13 Correct 2 ms 860 KB good job!
14 Correct 1 ms 604 KB good job!
15 Correct 1 ms 604 KB good job!

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 32764 KB good job!
2 Correct 133 ms 23780 KB good job!
3 Correct 420 ms 32668 KB good job!
4 Correct 149 ms 23896 KB good job!
5 Correct 392 ms 32680 KB good job!
6 Correct 127 ms 23892 KB good job!
7 Correct 141 ms 23824 KB good job!
8 Correct 394 ms 32596 KB good job!
9 Correct 385 ms 32708 KB good job!
10 Correct 385 ms 32596 KB good job!
11 Correct 471 ms 84664 KB good job!
12 Correct 276 ms 27844 KB good job!
13 Correct 490 ms 84564 KB good job!
14 Correct 268 ms 27712 KB good job!
15 Correct 146 ms 23816 KB good job!
16 Correct 131 ms 23772 KB good job!