Submission #1254296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254296		WhipppedCream	Hieroglyphs (IOI24_hieroglyphs)	C++20	10 / 100	19 ms	3788 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <vector>

using namespace std;

bool isSubseq(vector<int> A, vector<int> B) {
  int n = A.size(), m = B.size();
  int cur = 0;
  for (int i = 0; i < n; i++) {
    while(cur < m && A[i] != B[cur]) {
      cur++;
    }
    if (cur == m) {
      return false;
    }
    cur++;
  }
  return true;
}

int myCount(vector<int> C, int x) {
  int n = C.size();
  int res = 0;
  for (int i = 0; i < n; i++) {
    if (C[i] == x) {
      res++;
    }
  }
  return res;
}

vector<int> repeat(int n, int x) {
  vector<int> res;
  for (int i = 0; i < n; i++) {
    res.push_back(x);
  }
  return res;
}

vector<int> ucs(vector<int> A, vector<int> B) {
  int pref = 0;
  int n = A.size(), m = B.size();
  while(pref < min(n, m)) {
    if (A[pref] == B[pref]) {
      pref++;
    } else {
      break;
    }
  }
  int suf = 0;
  while(suf < min(n, m)) {
    if (A[n-(suf+1)] == B[m-(suf+1)]) {
      suf++;
    }
    else {
      break;
    }
  }

  if (pref == min(n, m) || suf == min(n, m)) {
    if (A.size() > B.size()) {
      swap(A, B);
    }
    return A;
  }

  vector<int> Ap, Bp;
  vector<int> prefix, suffix;
  for (int i = 0; i < pref; i++) {
    prefix.push_back(A[i]);
  }
  for (int i = pref; i < n-suf; i++) {
    Ap.push_back(A[i]);
  }
  for (int i = pref; i < m-suf; i++) {
    Bp.push_back(B[i]);
  }
  for (int i = n-suf; i < n; i++) {
    suffix.push_back(A[i]);
  }

  // for (int i = 0; i < (int) Ap.size(); i++) {
  //   printf(stderr, "%d ", Ap[i]);
  // }

  // printf("\n");

  // for (int i = 0; i < (int) Bp.size(); i++) {
  //   printf(stderr, "%d ", Bp[i]);
  // }

  vector<int> midAns;
  if (myCount(Ap, 0) == 0 || myCount(Bp, 0) == 0) {
    int a1 = myCount(Ap, 1);
    int b1 = myCount(Bp, 1);
    int x = min(a1, b1);
    midAns = repeat(x, 1);
  } else if (myCount(Ap, 1) == 0 || myCount(Bp, 1) == 0) {
    int a0 = myCount(Ap, 0);
    int b0 = myCount(Bp, 0);
    int x = min(a0, b0);
    midAns = repeat(x, 0);
  } else {
    if (Ap.size() > Bp.size()) {
      swap(Ap, Bp);
    }
    if (isSubseq(Ap, Bp)) {
      midAns = Ap;
    } else {
      vector<int> ans;
      ans.push_back(-1);
      return ans;
    }
  }


  vector<int> res = prefix;

  for (int i = 0; i < (int) midAns.size(); i++) {
    res.push_back(midAns[i]);
  }
  for (int i = 0; i < (int) suffix.size(); i++) {
    res.push_back(suffix[i]);
  }
  return res;
}

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