제출 #1217876

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

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

std::vector<int> ucs(std::vector<int> A, std::vector<int> B) {
  //A veya B'de yoksa sil
  //her elemanın minimum geçme sayısı kadar olmalı
  //0 0 1 1 2
  //2 0 1 2
  //bütün charları içeren bi common subsequence var mı
  //1 tane içercek A veya B
  //ona göre fixleyip orderlayıp kontrol edelim;
  vi at,bt;
  map<int,int> ao,bo,ap,bp;
  for (auto it : A) ao[it]++;
  for (auto it : B) bo[it]++;
  for (auto it : A) if (bo[it]) at.push_back(it);
  for (auto it : B) if (ao[it]) bt.push_back(it);
  A = at,B = bt;
  vector<pii> ps;
  vi v;
  ao.clear(),bo.clear();
  int posit = 0;
  for (auto it : A) {
    v.push_back(it);
    ao[it]++;
    ap[it] = posit++;
  }
  posit = 0;
  for (auto it : B) {
    v.push_back(it);
    bo[it]++;
    bp[it] = posit++;
  }
  sort(all(v));
  v.erase(unique(all(v)),v.end());
  sort(all(v),[&](int x,int y) {
    int p1,p2;
    if (ao[x] == 1) p1 = ap[x];
    else p1 = bp[x];
    if (ao[y] == 1) p2 = ap[y];
    else p2 = bp[y];
    return p1 < p2;
  });
  auto contains = [&](vi v1,vi v2) -> bool {
    int ptr = 0;
    for (auto it : v1) {
      if (ptr == v2.size()) return true;
      if (it == v2[ptr]) {
        ptr++;
      }
    }
    return ptr== v2.size();
  };
  vi Arev = A,Brev = B;
  reverse(all(Arev)),reverse(all(Brev));
  bool f1 = contains(A,v) && contains(B,v);
  sort(all(v),[&](int x,int y) {
    int p1,p2;
    if (ao[x] == 1) p1 = ap[x];
    else p1 = bp[x];
    if (ao[y] == 1) p2 = ap[y];
    else p2 = bp[y];
    return p1 > p2;
  });
  bool f2 = contains(Arev,v) && contains(Brev,v);
  if (!f1) return {-1};
  if (f1 && f2) return {-1};
  return v;
}

• 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