Submission #1193551

#TimeUsernameProblemLanguageResultExecution timeMemory
1193551KG07상형문자열 (IOI24_hieroglyphs)C++20
0 / 100
1132 ms1611892 KiB
#include "hieroglyphs.h" #include <bits/stdc++.h> using namespace std; vector<int> I = {-1}; struct segment_tree{ int n; int M[300000]; void init(int N, int l, int r){ if(l == r)M[N] = n; else{ init(2*N, l, (l+r)/2); init(2*N+1, (l+r)/2+1, r); } } void update(int N, int x, int y, int l, int r){ if(x < l || x > r)return; if(l == x && x == r){ M[N] = min(M[N], y); return; } update(2*N, x, y, l, (l+r)/2); update(2*N+1, x, y, (l+r)/2+1, r); M[N] = min(M[2*N], M[2*N+1]); } int get_left(int N, int z, int l, int r){ if(z < l)return n; if(z >= r)return M[N]; return min(get_left(2*N, z, l, (l+r)/2), get_left(2*N+1, z, (l+r)/2+1, r)); } int get_right(int N, int z, int l, int r){ if(z > r)return n; if(z <= l)return M[N]; return min(get_right(2*N, z, l, (l+r)/2), get_right(2*N+1, z, (l+r)/2+1, r)); } } T; struct indexes{ vector<int> A[200002], B[200002], C, D, E; int F[200002]; vector<pair<pair<int, int>, pair<int, int>>> e, f; bool is_sq(int a, int b, int c, int d){ return A[a][c-1] < A[b][A[b].size()-d] && B[a][c-1] < B[b][B[b].size()-d]; } bool init(vector<int> a, vector<int> b){ for(int i = 0; i < a.size(); i++)A[a[i]].push_back(i); for(int i = 0; i < b.size(); i++)B[b[i]].push_back(i); C.clear(), D.clear(), E.clear(); for(int i:a)if(A[i].size() <= B[i].size())C.push_back(i); for(int i:b)if(A[i].size() >= B[i].size())D.push_back(i); int N = C.size(); int M = D.size(); int x = 0, y = 0; while(x < N || y < M){ if(x || y)F[E[E.size()-1]]++; e.push_back(make_pair(make_pair(0, 0), make_pair(0, 0))); f.push_back(make_pair(make_pair(0, 0), make_pair(0, 0))); if(x == N){ E.push_back(D[y++]); continue; } if(y == M){ E.push_back(C[x++]); continue; } if(A[C[x]].size() == B[C[x]].size() || A[D[y]].size() == B[D[y]].size()){ if(C[x] == D[y]){ E.push_back(D[y++]); x++; continue; } if(A[C[x]].size() != B[C[x]].size()){ E.push_back(C[x++]); continue; } if(A[D[y]].size() != B[D[y]].size()){ E.push_back(D[y++]); continue; } return true; } bool X = is_sq(C[x], D[y], F[C[x]]+1, B[D[y]].size()-F[D[y]]), Y = is_sq(D[y], C[x], F[D[y]]+1, A[C[x]].size()-F[C[x]]); if(X && Y)return true; if(Y){ E.push_back(D[y++]); continue; } if(X){ E.push_back(C[x++]); continue; } return true; } return false; } bool check_sq(vector<int> a, vector<int> b){ for(int i:E)F[i] = 0; T.init(1, 1, T.n); for(int i = 0; i < E.size(); i++){ if(!F[E[i]])e[i].first.first = A[E[i]][0]; else{ int t = T.get_right(1, F[E[i]], 1, T.n); int l = 0, r = A[E[i]].size()-1; while(l < r){ int c = (l+r)/2; if(A[E[i]][c] > t)r = c; else l = c+1; } e[i].first.first = A[E[i]][l]; } F[E[i]] = i+1; T.update(1, i+1, e[i].first.first, 1, T.n); } for(int i:E)F[i] = T.n; T.init(1, 1, T.n); for(int i = E.size()-1; i >= 0; i--){ if(F[E[i]] == T.n)e[i].first.second = A[E[i]][A[E[i]].size()-1]; else{ int t = T.n-T.get_left(1, F[E[i]]+1, 1, T.n); int l = 0, r = A[E[i]].size()-1; while(l < r){ int c = (l+r+1)/2; if(A[E[i]][c] < t)l = c; else r = c-1; } e[i].first.second = A[E[i]][r]; } F[E[i]] = i; T.update(1, i+1, T.n-e[i].first.second, 1, T.n); } for(int i:E)F[i] = 0; T.init(1, 1, T.n); for(int i = 0; i < E.size(); i++){ if(!F[E[i]])e[i].second.first = B[E[i]][0]; else{ int t = T.get_right(1, F[E[i]], 1, T.n); int l = 0, r = B[E[i]].size()-1; while(l < r){ int c = (l+r)/2; if(B[E[i]][c] > t)r = c; else l = c+1; } e[i].second.first = B[E[i]][l]; } F[E[i]] = i+1; T.update(1, i+1, e[i].second.first, 1, T.n); } for(int i:E)F[i] = T.n; T.init(1, 1, T.n); for(int i = E.size()-1; i >= 0; i--){ if(F[E[i]] == T.n)e[i].second.second = B[E[i]][B[E[i]].size()-1]; else{ int t = T.n-T.get_left(1, F[E[i]]+1, 1, T.n); int l = 0, r = B[E[i]].size()-1; while(l < r){ int c = (l+r+1)/2; if(B[E[i]][c] < t)l = c; else r = c-1; } e[i].second.second = B[E[i]][r]; } F[E[i]] = i; T.update(1, i+1, T.n-e[i].second.second, 1, T.n); } int c, d; c = 0, d = 0; for(int i = 0; i < E.size(); i++){ while(a[c] != E[i])c++; f[i].first.first = c++; while(b[d] != E[i])d++; f[i].second.first = d++; } c = a.size()-1, d = b.size()-1; for(int i = E.size()-1; i >= 0; i--){ while(a[c] != E[i])c--; f[i].first.second = c--; while(b[d] != E[i])d--; f[i].second.second = d--; } T.n = a.size(); T.init(1, 1, T.n); for(int i = 0; i < E.size(); i++){ if(A[E[i]].size() <= B[E[i]].size())T.update(1, f[i].first.first, e[i].second.first, 1, T.n); if(B[E[i]].size() <= A[E[i]].size() && f[i].second.second <= T.get_right(1, e[i].first.second, 1, T.n))return true; } T.n = b.size(); T.init(1, 1, T.n); for(int i = 0; i < E.size(); i++){ if(B[E[i]].size() <= A[E[i]].size())T.update(1, f[i].second.first, e[i].first.first, 1, T.n); if(A[E[i]].size() <= B[E[i]].size() && f[i].first.second <= T.get_right(1, e[i].second.second, 1, T.n))return true; } return false; } } H; vector<int> ucs(vector<int> A, vector<int> B) { int N = A.size(), M = B.size(); if(H.init(A, B))return I; T.n = H.E.size(); if(H.check_sq(A, B))return I; return H.E; }
#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...