Submission #1203674

#TimeUsernameProblemLanguageResultExecution timeMemory
1203674AndreyHieroglyphs (IOI24_hieroglyphs)C++20
0 / 100
38 ms15940 KiB
#include "hieroglyphs.h" #include <vector> #include<bits/stdc++.h> using namespace std; vector<int> pos1[200001]; vector<int> pos2[200001]; int dude(int x, int a) { int l = 0,r = pos1[x].size()-1; while(l < r) { int mid = (l+r)/2; if(pos1[x][mid] >= a) { r = mid; } else { l = mid+1; } } return pos1[x][l]; } std::vector<int> ucs(std::vector<int> a, std::vector<int> b) { vector<int> wow(0); vector<int> wut(1,-1); for(int i = 0; i < a.size(); i++) { pos1[a[i]].push_back(i); } for(int i = 0; i < b.size(); i++) { pos2[b[i]].push_back(i); } for(int i = 0; i < a.size(); i++) { if(pos1[a[i]].size() <= pos2[a[i]].size()) { wow.push_back(a[i]); wut.push_back(i); } } cout << wow.size() << endl; int y = wow.size()-1; vector<int> banana(b.size()); for(int i = b.size()-1; i >= 0; i--) { if(y >= 0 && b[i] == wow[y]) { y--; } banana[i] = y+1; } vector<int> ans(0); y = 1; int l = 0; for(int i = 0; i < b.size(); i++) { if(pos1[b[i]].size() <= pos2[b[i]].size()) { continue; } l = max(l,wut[banana[i]]+1); int c = dude(b[i],l); l = max(l,c+1); while(y < wut.size() && wut[y] < c) { ans.push_back(wow[y-1]); y++; } ans.push_back(b[i]); } while(y < wut.size()) { ans.push_back(wow[y-1]); y++; } 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...