제출 #1203001

#제출 시각아이디문제언어결과실행 시간메모리
1203001alir3za_zar3Watermelon (INOI20_watermelon)C++20
100 / 100
80 ms31816 KiB
// Alir3za.Zar3 -> Shiraz , Iran #include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 1e5+7; int n,k , a[maxn],in[maxn],np=0; vector<int> e[maxn]; vector<int> val(maxn),out(maxn); set<int> source; void permut (int q) { if (source.empty()) { if (++np == k) out = val; return; } vector<int> sou; int sz = 0; for (auto v : source) { if (sz < 10) sou.push_back(v) , sz++; else break; } for (auto v : sou) { source.erase(v); val[v] = q; for (auto to : e[v]) if (--in[to] == 0) source.insert(to); permut(q+1); if (np >= k) return; val[v] = 0; source.insert(v); for (auto to : e[v]) if (++in[to] == 1) source.erase(to); } } signed main () { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i=1; i<=n; i++) cin >> a[i]; if (a[n] != -1) { cout << -1 << '\n'; return 0; } vector<int> st; st.push_back(n); bool eraser = true; for (int i=n-1; i; i--) { int dp = 0; if (a[i] == -1) { while(!st.empty()) { int v = st.back(); e[v].push_back(i); in[i]++; st.pop_back(); } st.push_back(i); continue; } while (!st.empty()) { int v = st.back(); if (a[v] == -1 or a[v] >= a[i]) { if (a[i] != dp+1) eraser = false; e[i].push_back(v); st.push_back(i); in[v]++; break; } else if (a[v] > dp) { dp = a[v]; e[v].push_back(i); in[i]++; } st.pop_back(); } st.push_back(i); } if (!eraser) { cout << -1 << '\n'; return 0; } vector<int> val(maxn); for (int i=1; i<=n; i++) if (!in[i]) source.insert(i); permut(1); if (np < k) { cout << -1 << '\n'; return 0; } for (int i=1; i<=n; i++) cout << out[i] << ' '; cout << '\n'; }
#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...