제출 #1222009

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222009		hyakup	상형문자열 (IOI24_hieroglyphs)	C++20	0 / 100	951 ms	2162688 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> ucs(vector<int> a, vector<int> b) {
  int n = a.size(), m = b.size();
  vector<vector<int>> dp(n + 1, vector<int>(m + 1)), last( n + 1, vector<int>(m + 1, -1));
  for( int i = 1; i < n; i++ ){
    for( int j = 1; j < m; j++ ){
      if( dp[i - 1][j] == dp[i][j - 1] ){
        if( last[i - 1][j] != last[i][j - 1] ) return vector<int>(1, -1);
      }
      if( a[i - 1] == b[j - 1] ){
        dp[i][j] = dp[i - 1][j - 1] + 1;
        last[i][j] = a[i - 1];
      }
      else{
        dp[i][j] = max( dp[i - 1][j], dp[i][j - 1] );
        if( dp[i - 1][j] == dp[i][j - 1] ){
          if( last[i - 1][j] != last[i][j - 1] ) return vector<int>(1, -1);
          last[i][j] = last[i - 1][j];
        }
        else if( dp[i - 1][j] > dp[i][j - 1] ) last[i][j] = last[i - 1][j];
        else last[i][j] = last[i][j - 1];
      }
    }
  }

  int i = n + 1, j = m + 1;
  vector<int> resp;
  while( i > 0 && j > 0 ){
    if( a[i - 1] == b[j - 1] ){
      resp.push_back(a[i - 1]);
      i--; j--;
    }
    else{
      if( dp[i - 1][j] > dp[i][j - 1] ) i--;
      else j--;
    }
  }
  reverse( resp.begin(), resp.end() );
  return resp;
}

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