Submission #627055

#	Time	Username	Problem	Language	Result	Execution time	Memory
627055		AA_Surely	Watermelon (INOI20_watermelon)	C++14	31 / 100	21 ms	3468 KiB

Main

#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int N = 1e5 + 7;
const int LOG = 22;
const int INF = 1e9 + 7;

int n, k;
int ns[N], ans[N], adj[N];
int lst[N], pl[N], big[N];
PII st[N];

int change() {
    int bc = 0, oc = 0;
    F0R(i, n) {
        if (ns[i] == n + 1) bc++;
        if (ns[i] == 1) oc++;
    }

    if (!oc || (oc == 1 && bc == 1)) return cout << -1, 0;

    if (bc > 1) {
        int pl = -1;
        F0R(i, n) if (ns[i] == 1) pl = i;
        while(adj[pl] != -1) pl = adj[pl];
        assert(ans[pl] + 1 == ans[n - 1]);
        swap(ans[pl], ans[n - 1]);
    }

    else {
        int pl1 = -1;
        F0R(i, n) if (ns[i] == 1) pl1 = i;

        int pl2 = -1;
        F0R(i, pl1) if (ns[i] == 1) pl2 = i;
        while(adj[pl2] != -1) pl2 = adj[pl2];

        swap(ans[pl1], ans[pl2]);
    }

    F0R(i, n) cout << ans[i] << ' ';
    return 0;
}

int main() {
    IOS;

    cin >> n >> k;
    F0R(i, n) cin >> ns[i];

    if (ns[n - 1] != -1) return cout << -1, 0;
    F0R(i, n) if (ns[i] == -1) ns[i] = n + 1;
    
    fill(pl, pl + n + 2, n + 1);
    fill(adj, adj + n, -1);
    R0F(i, n) {
        pl[ ns[i] ] = i;
        if (ns[i] == n + 1) continue;

        if (ns[i] == 1) lst[i] = i;
        else {
            lst[i] = pl[ ns[i] - 1 ];
            adj[ pl[ ns[i] - 1 ] ] = i;
        }
    }

    stack<int> keep;
    R0F(i, n) {
        while(!keep.empty() && ns[keep.top()] < ns[i]) keep.pop();
        big[i] = n + 1;
        if (!keep.empty()) big[i] = keep.top();

        keep.push(i);
    }

    F0R(i, n) if (ns[i] != 1 && ns[i] != n + 1)
        if (lst[i] > big[i]) return cout << -1, 0;
    
    int v = 1;
    F0R(i, n) if (ns[i] == 1) {
        int now = i;
        while(now != -1) {
            ans[now] = v++;
            now = adj[now];
        }
    }
    R0F(i, n) if (ns[i] == n + 1) ans[i] = v++;

    if (k == 2) change();
    else F0R(i, n) cout << ans[i] << ' ';
}

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