Submission #1242316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242316		SalihSahin	상형문자열 (IOI24_hieroglyphs)	C++20	3 / 100	110 ms	26820 KiB

hieroglyphs

#include "hieroglyphs.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back

const int MAXA = 2e5 + 5;

struct SEGT{
  vector<array<int, 3> > tree;

  void init(int n){
    tree.assign(4*n, {0, 0, 0});
  }

  void update(int ind, int l, int r, int pos, array<int, 3> val){
    if(l == r){
      tree[ind] = max(tree[ind], val);
    }
    else{
      int m = (l + r)/2;

      if(pos <= m) update(ind*2, l, m, pos, val);
      else update(ind*2+1, m+1, r, pos, val);

      tree[ind] = max(tree[ind*2], tree[ind*2+1]);
    }
  }

  array<int, 3> query(int ind, int l, int r, int ql, int qr){
    if(l > r || ql > qr || l > qr || r < ql) return {0, 0, 0};
    if(l >= ql && r <= qr){
      return tree[ind];
    }
    else{
      int m = (l + r)/2;

      return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr));
    }
  }
};

vector<int> ucs(vector<int> A, vector<int> B){
  int n = A.size(), m = B.size();

  vector<int> ind[MAXA];
  for(int i = 0; i < m; i++){
    ind[B[i]].pb(i+1);
  }

  vector<int> cnt(MAXA);
  for(int i = 0; i < n; i++){
    cnt[A[i]] = 1;
  }
  for(int i = 0; i < m; i++){
    if(cnt[B[i]] == 1){
      cnt[B[i]] = 2;
    }
  }

  for(int i = 0; i < MAXA; i++){
    if(ind[i].size() == 1){
      ind[i].pb(ind[i][0]);
    }
  }

  vector<vector<int> > dp(n, vector<int>(2));
  vector<vector<pair<int, int> > > par(n, vector<pair<int, int> >(2));
  SEGT seg;
  seg.init(m);
  array<int, 3> maxlis = {0, 0, 0};

  for(int i = 0; i < n; i++){
    if(ind[A[i]].size() == 0) continue; // b de bu eleman yok

    for(int j = 0; j < 2; j++){
      int pos2 = ind[A[i]][j];
      array<int, 3> arr = seg.query(1, 1, m, 1, pos2 - 1);
      if(arr[0] + 1 > dp[i][j]){
        dp[i][j] = max(dp[i][j], arr[0] + 1);
        par[i][j] = {arr[1], arr[2]};
      }
      maxlis = max(maxlis, {dp[i][j], i, j});
    }
    for(int j = 0; j < 2; j++){
      int pos2 = ind[A[i]][j];
      seg.update(1, 1, m, pos2, {dp[i][j], i, j});
    }
  }

  // condition 1: 2 farklı max size candidate olamaz (1 tane varsa onu checkleyecegiz) ve bu butun subseqleri kapsamalı
  // birden fazla degerden lis alabilen i, j degerleri bad; sondan geriye tracklerken bad node yoksa devam
  // condition 2: max size candidate degerim butun ortak elemanları kapsamalı => 1 ve 2 size olanlar için sağlaması yeterli (k <= 3)
  bool checklen1 = 1;
  int same = 0;
  for(int i = 0; i < MAXA; i++){
    if(cnt[i] == 2){
      same++;
    }
  }
  if(same != maxlis[0]){
    checklen1 = 0;
  }

  vector<int> ans;
  pair<int, int> p = {maxlis[1], maxlis[2]};
  while(p != make_pair(0, 0)){
    ans.pb(A[p.first]);
    p = par[p.first][p.second];
  }
  reverse(ans.begin(), ans.end());
  /*
  for(auto itr: ans){
    cout<<itr<<" ";
  }
  cout<<endl;
  */

  bool checklen2 = 1; // x...y...x,  y...x...y gelirse 2 farklı order oldugundan -1 yoksa ans yazdırcaz
  if(!checklen1 || !checklen2) return {-1};
  else return ans;
}

• 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