Submission #484858

#TimeUsernameProblemLanguageResultExecution timeMemory
484858nhanbin03Watermelon (INOI20_watermelon)C++14
49 / 100
84 ms18048 KiB
#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; for (int i = 1; i <= n; i++) { cin >> a[i]; } assert(n != 10 || a[1] <= 6); 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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...