Submission #1241249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241249		rxlfd314	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	30 ms	2632 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

vt<int> ucs(vt<int> A, vt<int> B) {
  const int N = size(A), M = size(B);
  bool sub1 = N == M;
  vt<int> temp = A;
  sort(all(temp));
  FOR(i, 0, N-1)
    sub1 &= temp[i] == i;
  temp = B;
  sort(all(temp));
  FOR(i, 0, M-1)
    sub1 &= temp[i] == i;
  if (sub1)
    return A == B ? A : vt<int>{-1};
  if (max(N, M) <= 3000) {
    A.insert(A.begin(), 0);
    B.insert(B.begin(), 0);
    vt<vt<int>> dp(N+1, vt<int>(M+1));
    vt<vt<pair<int, int>>> par(N+1, vt<pair<int, int>>(M+1));
    FOR(i, 1, N)
      FOR(j, 1, M) {
        dp[i][j] = max({dp[i-1][j-1] + (A[i] == B[j]), dp[i-1][j], dp[i][j-1]});
        if (A[i] == B[j] && dp[i-1][j-1] + 1 == dp[i][j])
          par[i][j] = {i-1, j-1};
        else if (dp[i-1][j] == dp[i][j])
          par[i][j] = {i-1, j};
        else
          par[i][j] = {i, j-1};
      }
    vt<int> ans;
    for (int i = N, j = M; i && j; ) {
      const auto &[x, y] = par[i][j];
      if (x < i && y < j) {
        #ifdef DEBUG
        cout << "added: " << i << ' ' << j << '\n';
        #endif
        ans.push_back(A[i]);
      }
      i = x, j = y;
    }
    reverse(all(ans));
    constexpr int MAX = 200005;
    vt<int> cnt_A(MAX), cnt_B(MAX);
    FOR(i, 1, N)
      cnt_A[A[i]]++;
    FOR(i, 1, M)
      cnt_B[B[i]]++;
    int must = 0;
    FOR(i, 0, MAX-1)
      must += min(cnt_A[i], cnt_B[i]);
    #ifdef DEBUG
    cout << "must: " << must << '\n';
    #endif
    return size(ans) < must ? vt<int>{-1} : ans;
  }
}

Compilation message (stderr)

hieroglyphs.cpp: In function 'vt<int> ucs(vt<int>, vt<int>)':
hieroglyphs.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
   70 | }
      | ^

• 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