Submission #1202986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202986		alir3za_zar3	Watermelon (INOI20_watermelon)	C++20	32 / 100	976 ms	1114112 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],out(maxn);

void permut 
(set<int> source , vector<int> val , int q)
{
    if (source.empty())
    {
        if (++np == k) out = val;
        return;
    }
    for (auto v : source)
    {
        set<int> nxt = source;
        nxt.erase(v);
        val[v] = q;
        for (auto to : e[v])
            if (--in[to] == 0)
                nxt.insert(to);
        permut(nxt , val , q+1);
        if (np >= k) return;
        val[v] = 0;
        for (auto to : e[v]) ++in[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;
    }
    set<int> source;
    vector<int> val(maxn);
    for (int i=1; i<=n; i++)
        if (!in[i]) source.insert(i);
    permut(source , val , 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: 0 / 31
• Subtask 4: 0 / 18
• Subtask 5: 0 / 19