Submission #1203001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203001		alir3za_zar3	Watermelon (INOI20_watermelon)	C++20	100 / 100	80 ms	31816 KiB

Main

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5+7;
int n,k , a[maxn],in[maxn],np=0;
vector<int> e[maxn];
vector<int> val(maxn),out(maxn);
set<int> source;

void permut 
(int q)
{
    if (source.empty())
    {
        if (++np == k) out = val;
        return;
    }
    vector<int> sou;
    int sz = 0;
    for (auto v : source)
    {
        if (sz < 10)
            sou.push_back(v) , sz++;
        else break;
    }
        
    
    for (auto v : sou)
    {
        source.erase(v);
        val[v] = q;
        for (auto to : e[v])
            if (--in[to] == 0)
                source.insert(to);
        permut(q+1);
        if (np >= k) return;
        val[v] = 0;
        source.insert(v);
        for (auto to : e[v]) 
            if (++in[to] == 1)
                source.erase(to);
    }
}

signed main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
    
    cin >> n >> k;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    if (a[n] != -1)
    {
        cout << -1 << '\n';
        return 0;
    }
    vector<int> st;
    st.push_back(n);
    bool eraser = true;
    for (int i=n-1; i; i--)
    {
        int dp = 0;
        if (a[i] == -1)
        {
            while(!st.empty())
			{
				int v = st.back();
				e[v].push_back(i); in[i]++;
				st.pop_back();
			}
            st.push_back(i);
            continue;
        }
        while (!st.empty())
        {
            int v = st.back();
            if (a[v] == -1 or a[v] >= a[i])
            {
                if (a[i] != dp+1) 
                    eraser = false;
                e[i].push_back(v);
                st.push_back(i); in[v]++; 
                break;
            }
            else if (a[v] > dp)
            {
                dp = a[v];
                e[v].push_back(i);
                in[i]++;
            }
            st.pop_back();
        }
        st.push_back(i);
    }
    if (!eraser)
    {
        cout << -1 << '\n';
        return 0;
    }
    vector<int> val(maxn);
    for (int i=1; i<=n; i++)
        if (!in[i]) source.insert(i);
    permut(1);
    if (np < k)
    {
        cout << -1 << '\n';
        return 0;
    }
    for (int i=1; i<=n; i++)
        cout << out[i] << ' ';
    cout << '\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 18 / 18
• Subtask 5: 19 / 19