제출 #1213212

#제출 시각아이디문제언어결과실행 시간메모리
1213212onbertHieroglyphs (IOI24_hieroglyphs)C++20
0 / 100
1096 ms25540 KiB
#include "hieroglyphs.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5, maxval = 2e5 + 5; int n, m; vector<int> a, b; int afreq[maxval], bfreq[maxval]; vector<int> apos[maxval], bpos[maxval]; vector<pair<int,int>> acrit, bcrit; int asz, bsz; int l[maxn], r[maxn]; vector<int> vec[maxn]; int aqry(int val, int l, int r) { if (l > r) return 0; return upper_bound(apos[val].begin(), apos[val].end(), r) - lower_bound(apos[val].begin(), apos[val].end(), l); } int bqry(int val, int l, int r) { if (l > r) return 0; return upper_bound(bpos[val].begin(), bpos[val].end(), r) - lower_bound(bpos[val].begin(), bpos[val].end(), l); } int af[maxval], bf[maxval]; bool ok(int id) { for (int i=0;i<maxval;i++) af[i] = bf[i] = 0; int apt = l[id], bpt = bcrit[id].second; int cnt = 0, siz = 0; for (int i=id+1;i<bsz;i++) { siz += vec[i-1].size(); while (apt < r[i]) { apt++; int val = a[apt]; if (afreq[val] < bfreq[val]) { cnt -= min(af[val], bf[val]); af[val]++; cnt += min(af[val], bf[val]); } } while (bpt < bcrit[i].second) { bpt++; int val = b[bpt]; if (afreq[val] < bfreq[val]) { cnt -= min(af[val], bf[val]); bf[val]++; cnt += min(af[val], bf[val]); } } if (cnt != siz) return 0; } return 1; } vector<int> ucs(vector<int> A, vector<int> B) { for (int i:A) afreq[i]++; for (int i:B) bfreq[i]++; a.push_back(2e5 + 1), b.push_back(2e5 + 1); for (int i:A) if (bfreq[i]) a.push_back(i); for (int i:B) if (afreq[i]) b.push_back(i); a.push_back(2e5 + 2), b.push_back(2e5 + 2); n = a.size(), m = b.size(); for (int i=0;i<n;i++) if (afreq[a[i]] < bfreq[a[i]]) { acrit.push_back({a[i], i}); } for (int i=0;i<m;i++) if (bfreq[b[i]] <= afreq[b[i]]) { bcrit.push_back({b[i], i}); } asz = acrit.size(), bsz = bcrit.size(); for (int i=0;i<n;i++) apos[a[i]].push_back(i); for (int i=0;i<m;i++) bpos[b[i]].push_back(i); int pt = bsz; for (int i=n-1;i>=0;i--) if (pt-1 >= 0 && bcrit[pt-1].first == a[i]) pt--, r[pt] = i; pt = -1; for (int i=0;i<n;i++) if (pt+1 < bsz && bcrit[pt+1].first == a[i]) pt++, l[pt] = i; if (pt != bsz-1) return {-1}; vector<int> ans; int apt = -1, bpt = -1, nxt = -1; for (int i=0;i<bsz;i++) { auto [val, pos] = bcrit[i]; // cout << "i " << i << endl; while (apt+1 < asz && acrit[apt+1].second < r[i] && bpt < pos) { bpt++; if (b[bpt] == acrit[apt+1].first) { vec[i-1].push_back({b[bpt]}); ans.push_back(b[bpt]); apt++; // cout << acrit[apt].second << endl; } } if (i != 0 && i != bsz-1) ans.push_back(val); nxt = *upper_bound(apos[val].begin(), apos[val].end(), nxt); if (apt != -1) nxt = max(*upper_bound(apos[val].begin(), apos[val].end(), acrit[apt].second), nxt); // cout << "thing " << i-1 << " " << val << " " << apt << endl; // cout << acrit[apt].second << " " << acrit[apt+1].second << " " << nxt << endl; if (apt+1 < asz && acrit[apt+1].second < nxt) return {-1}; bpt = pos; } if (ans.size() + 2 != asz + bsz) return {-1}; // for (int i=0;i<bsz-1;i++) if (!ok(i)) return {-1}; for (int i=0;i<bsz-1;i++) if (!ok(i)) return {-1}; // for (int i=0;i<bsz-1;i++) if (!ok(i, i+1)) return {-1}; return ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...