Submission #1193238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193238		KG07	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	40 ms	20396 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> I = {-1};
struct indexes{
  vector<int> A[200002], B[200002], C, D, E;
  int F[200002];
  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]]++;
      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++]);
          y++;
          continue;
        }
        if(A[D[y]].size() != B[D[y]].size()){
          E.push_back(D[y++]);
          x++;
          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;
  }
} H;

vector<int> ucs(vector<int> A, vector<int> B) {
  int N = A.size(), M = B.size();
  if(H.init(A, B))return I;
  return H.E;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 16
• Subtask 5: 0 / 14
• Subtask 6: 0 / 42