oj.uz

Submission #484826

# Submission time Handle Problem Language Result Execution time Memory
484826 2021-11-05T14:55:31 Z nhanbin03 Watermelon (INOI20_watermelon) C++14
31 / 100
 80 ms 18080 KB 
#include <bits/stdc++.h>
#define task "INOI20_watermelon"
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5 + 10;

int n, k;
int a[N], inDeg[N], ans[N], rev[N];
vector<int> adj[N], pos[N];

bool buildDAG(int maxVal) {
    for (int i = 1; i <= n; i++) {
        pos[a[i]].push_back(i);
    }
    set<int> posSet;
    for (int i = maxVal; i >= 1; i--) {
        if (pos[i].empty()) return 0;
        for (int j = pos[i].size() - 1; j >= 0; j--)  {
            int x = pos[i][j];
            auto it = posSet.lower_bound(x);
            if (it != posSet.end()) {
                adj[x].push_back(*it);
                inDeg[*it]++;
            }
            if (it != posSet.begin()) {
                it--;
                if (j == 0 || pos[i][j - 1] < *it) {
                    adj[x].push_back(*it);
                    inDeg[*it]++;
                }
            }
            posSet.insert(x);
        }
    }
    return 1;
}

void solve() {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 1; i <= n; i++) {
        if (inDeg[i] == 0) {
            pq.push(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        int u = pq.top(); pq.pop();
        ans[u] = i;
        for (int v : adj[u]) {
            inDeg[v]--;
            if (inDeg[v] == 0) pq.push(v);
        }
    }
    for (int i = 1; i <= n; i++) {
        assert(inDeg[i] == 0);
        rev[ans[i]] = i;
    }
}

bool findNext() {
    set<int> s;
    for (int i = n; i >= 1; i--) {
        int u = rev[i];
//        cout << i << " " << u << endl;
        for (int v : adj[u]) {
            inDeg[v]++;
            s.erase(v);
        }
//        for (auto it = s.begin(); it != s.end(); it++) cout << *it << " "; cout << endl;
        auto it = s.lower_bound(u);
        if (it != s.end()) {
            priority_queue<int, vector<int>, greater<int>> pq;
            int u = *it;
            pq.push(u);
            for (int j = i; j <= n; j++) {
                int u = pq.top(); pq.pop();
                if (j == i) {
                    pq.push(rev[i]);
//                    cout << rev[i] << endl;
                    for (auto it = s.begin(); it != s.end(); it++) {
//                        cout << *it << " ";
                        if (*it != u) pq.push(*it);
                    }
//                    cout << endl;
                }
                ans[u] = j;
                for (int v : adj[u]) {
                    inDeg[v]--;
//                    cout << u << " " << v << " " << inDeg[v] << endl;
                    if (inDeg[v] == 0) pq.push(v);
                }
            }
            return 1;
        }
        s.insert(u);
    }
    return 0;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    if (fopen(task ".inp","r")) {
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }
    cin >> n >> k;
    assert(k == 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (a[n] != -1) {
        cout << -1;
        return 0;
    }
    int maxVal = 0;
    for (int i = 1; i <= n; i++) {
        maxVal = max(maxVal, a[i]);
    }
    for (int i = n; i >= 1; i--) {
        if (a[i] == -1) a[i] = ++maxVal;
    }
//    for (int i = 1; i <= n; i++) {
//        cout << a[i] << " ";
//    }
//    cout << "\n";
    if (!buildDAG(maxVal)) {
        cout << -1;
        return 0;
    }
//    for (int i = 1; i <= n; i++) {
//        cout << i << ": ";
//        for (int j : adj[i]) {
//            cout << j << " ";
//        }
//        cout << "\n";
//    }
    solve();
    for (int i = 1; i < k; i++) {
        if (!findNext()) {
            cout << -1;
            return 0;
        }
        for (int j = 1; j <= n; j++) {
//            cout << ans[j] << " ";
            assert(inDeg[j] == 0);
            rev[ans[j]] = j;
        }
//        cout << endl;
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    for (int u = 1; u <= n; u++) {
        for (int v : adj[u]) {
            if (ans[u] >= ans[v]) {
                assert(0);
            }
        }
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Incorrect 3 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Incorrect 3 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 10332 KB Output is correct
2 Correct 8 ms 5964 KB Output is correct
3 Correct 27 ms 10280 KB Output is correct
4 Correct 8 ms 5964 KB Output is correct
5 Correct 29 ms 10320 KB Output is correct
6 Correct 27 ms 10304 KB Output is correct
7 Correct 27 ms 10376 KB Output is correct
8 Correct 27 ms 10328 KB Output is correct
9 Correct 28 ms 10384 KB Output is correct
10 Correct 27 ms 10360 KB Output is correct
11 Correct 57 ms 15568 KB Output is correct
12 Correct 59 ms 15468 KB Output is correct
13 Correct 56 ms 15444 KB Output is correct
14 Correct 56 ms 15420 KB Output is correct
15 Correct 15 ms 6988 KB Output is correct
16 Correct 15 ms 7064 KB Output is correct
17 Correct 14 ms 6988 KB Output is correct
18 Correct 15 ms 7072 KB Output is correct
19 Correct 15 ms 6988 KB Output is correct
20 Correct 15 ms 7008 KB Output is correct
21 Correct 15 ms 6988 KB Output is correct
22 Correct 15 ms 6988 KB Output is correct
23 Correct 15 ms 7024 KB Output is correct
24 Correct 59 ms 16056 KB Output is correct
25 Correct 61 ms 16096 KB Output is correct
26 Correct 68 ms 16252 KB Output is correct
27 Correct 60 ms 15848 KB Output is correct
28 Correct 60 ms 15964 KB Output is correct
29 Correct 60 ms 15824 KB Output is correct
30 Correct 19 ms 8140 KB Output is correct
31 Correct 31 ms 10316 KB Output is correct
32 Correct 66 ms 14444 KB Output is correct
33 Correct 72 ms 15504 KB Output is correct
34 Correct 9 ms 6092 KB Output is correct
35 Correct 14 ms 7116 KB Output is correct
36 Correct 32 ms 10240 KB Output is correct
37 Correct 80 ms 15484 KB Output is correct
38 Correct 67 ms 15792 KB Output is correct
39 Correct 77 ms 15584 KB Output is correct
40 Correct 56 ms 16892 KB Output is correct
41 Correct 58 ms 18080 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 10332 KB Output is correct
2 Correct 8 ms 5964 KB Output is correct
3 Correct 27 ms 10280 KB Output is correct
4 Correct 8 ms 5964 KB Output is correct
5 Correct 29 ms 10320 KB Output is correct
6 Correct 27 ms 10304 KB Output is correct
7 Correct 27 ms 10376 KB Output is correct
8 Correct 27 ms 10328 KB Output is correct
9 Correct 28 ms 10384 KB Output is correct
10 Correct 27 ms 10360 KB Output is correct
11 Correct 57 ms 15568 KB Output is correct
12 Correct 59 ms 15468 KB Output is correct
13 Correct 56 ms 15444 KB Output is correct
14 Correct 56 ms 15420 KB Output is correct
15 Correct 15 ms 6988 KB Output is correct
16 Correct 15 ms 7064 KB Output is correct
17 Correct 14 ms 6988 KB Output is correct
18 Correct 15 ms 7072 KB Output is correct
19 Correct 15 ms 6988 KB Output is correct
20 Correct 15 ms 7008 KB Output is correct
21 Correct 15 ms 6988 KB Output is correct
22 Correct 15 ms 6988 KB Output is correct
23 Correct 15 ms 7024 KB Output is correct
24 Correct 59 ms 16056 KB Output is correct
25 Correct 61 ms 16096 KB Output is correct
26 Correct 68 ms 16252 KB Output is correct
27 Correct 60 ms 15848 KB Output is correct
28 Correct 60 ms 15964 KB Output is correct
29 Correct 60 ms 15824 KB Output is correct
30 Correct 19 ms 8140 KB Output is correct
31 Correct 31 ms 10316 KB Output is correct
32 Correct 66 ms 14444 KB Output is correct
33 Correct 72 ms 15504 KB Output is correct
34 Correct 9 ms 6092 KB Output is correct
35 Correct 14 ms 7116 KB Output is correct
36 Correct 32 ms 10240 KB Output is correct
37 Correct 80 ms 15484 KB Output is correct
38 Correct 67 ms 15792 KB Output is correct
39 Correct 77 ms 15584 KB Output is correct
40 Correct 56 ms 16892 KB Output is correct
41 Correct 58 ms 18080 KB Output is correct
42 Runtime error 6 ms 9932 KB Execution killed with signal 6
43 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Incorrect 3 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -