Submission #627028

#	Time	Username	Problem	Language	Result	Execution time	Memory
627028		AA_Surely	Watermelon (INOI20_watermelon)	C++14	0 / 100	4 ms	960 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) FOR(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];
int lst[N], pl[N], big[N];
PII st[N];

int main() {
    IOS;

    cin >> n >> k;
    F0R(i, n) cin >> ns[i];
    //F0R(i, n) cout << ns[i] << ' '; cout << endl;

    if (ns[n - 1] != -1) return cout << -1, 0;
    F0R(i, n) if (ns[i] == -1) ns[i] = n + 1;
    //F0R(i, n) cout << ns[i] << ' '; cout << endl;
    
    fill(lst, lst + n + 2, 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 ];
    }

    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;
    
    //F0R(i, n) cout << ns[i] << ' '; cout << endl;
    F0R(i, n) st[i] = {ns[i], i};
    sort(st, st + n);
    //F0R(i, n) cout << "(" << st[i].F << " " << st[i].S << ") "; cout << endl;

    int v = 1;
    F0R(i, n) ans[ st[i].S ] = v++;

    v = n;
    R0F(i, n) if (ns[i] == n + 1) ans[i] = v--;

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

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