oj.uz

Submission #484819

# Submission time Handle Problem Language Result Execution time Memory
484819 2021-11-05T14:45:17 Z nhanbin03 Watermelon (INOI20_watermelon) C++14
31 / 100
 83 ms 18084 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 != 2);
    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] << " ";
    }
}

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 2 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 2 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 30 ms 10296 KB Output is correct
2 Correct 9 ms 6040 KB Output is correct
3 Correct 32 ms 10260 KB Output is correct
4 Correct 9 ms 5952 KB Output is correct
5 Correct 29 ms 10292 KB Output is correct
6 Correct 28 ms 10300 KB Output is correct
7 Correct 28 ms 10312 KB Output is correct
8 Correct 27 ms 10244 KB Output is correct
9 Correct 30 ms 10376 KB Output is correct
10 Correct 28 ms 10268 KB Output is correct
11 Correct 55 ms 15424 KB Output is correct
12 Correct 61 ms 15484 KB Output is correct
13 Correct 59 ms 15480 KB Output is correct
14 Correct 56 ms 15544 KB Output is correct
15 Correct 15 ms 6988 KB Output is correct
16 Correct 15 ms 7072 KB Output is correct
17 Correct 15 ms 6988 KB Output is correct
18 Correct 16 ms 6992 KB Output is correct
19 Correct 15 ms 6992 KB Output is correct
20 Correct 15 ms 6988 KB Output is correct
21 Correct 15 ms 6988 KB Output is correct
22 Correct 20 ms 6988 KB Output is correct
23 Correct 15 ms 7096 KB Output is correct
24 Correct 61 ms 16068 KB Output is correct
25 Correct 64 ms 16068 KB Output is correct
26 Correct 59 ms 16196 KB Output is correct
27 Correct 61 ms 15812 KB Output is correct
28 Correct 60 ms 16004 KB Output is correct
29 Correct 62 ms 15908 KB Output is correct
30 Correct 18 ms 8140 KB Output is correct
31 Correct 32 ms 10308 KB Output is correct
32 Correct 67 ms 14444 KB Output is correct
33 Correct 72 ms 15556 KB Output is correct
34 Correct 7 ms 6048 KB Output is correct
35 Correct 13 ms 7092 KB Output is correct
36 Correct 32 ms 10272 KB Output is correct
37 Correct 83 ms 15596 KB Output is correct
38 Correct 63 ms 15856 KB Output is correct
39 Correct 73 ms 15556 KB Output is correct
40 Correct 57 ms 16940 KB Output is correct
41 Correct 60 ms 18084 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 10296 KB Output is correct
2 Correct 9 ms 6040 KB Output is correct
3 Correct 32 ms 10260 KB Output is correct
4 Correct 9 ms 5952 KB Output is correct
5 Correct 29 ms 10292 KB Output is correct
6 Correct 28 ms 10300 KB Output is correct
7 Correct 28 ms 10312 KB Output is correct
8 Correct 27 ms 10244 KB Output is correct
9 Correct 30 ms 10376 KB Output is correct
10 Correct 28 ms 10268 KB Output is correct
11 Correct 55 ms 15424 KB Output is correct
12 Correct 61 ms 15484 KB Output is correct
13 Correct 59 ms 15480 KB Output is correct
14 Correct 56 ms 15544 KB Output is correct
15 Correct 15 ms 6988 KB Output is correct
16 Correct 15 ms 7072 KB Output is correct
17 Correct 15 ms 6988 KB Output is correct
18 Correct 16 ms 6992 KB Output is correct
19 Correct 15 ms 6992 KB Output is correct
20 Correct 15 ms 6988 KB Output is correct
21 Correct 15 ms 6988 KB Output is correct
22 Correct 20 ms 6988 KB Output is correct
23 Correct 15 ms 7096 KB Output is correct
24 Correct 61 ms 16068 KB Output is correct
25 Correct 64 ms 16068 KB Output is correct
26 Correct 59 ms 16196 KB Output is correct
27 Correct 61 ms 15812 KB Output is correct
28 Correct 60 ms 16004 KB Output is correct
29 Correct 62 ms 15908 KB Output is correct
30 Correct 18 ms 8140 KB Output is correct
31 Correct 32 ms 10308 KB Output is correct
32 Correct 67 ms 14444 KB Output is correct
33 Correct 72 ms 15556 KB Output is correct
34 Correct 7 ms 6048 KB Output is correct
35 Correct 13 ms 7092 KB Output is correct
36 Correct 32 ms 10272 KB Output is correct
37 Correct 83 ms 15596 KB Output is correct
38 Correct 63 ms 15856 KB Output is correct
39 Correct 73 ms 15556 KB Output is correct
40 Correct 57 ms 16940 KB Output is correct
41 Correct 60 ms 18084 KB Output is correct
42 Runtime error 6 ms 9992 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 2 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -