Submission #1254749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254749		testaccount	Hieroglyphs (IOI24_hieroglyphs)	C++20	14 / 100	1098 ms	132104 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <vector>
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const int maxn=  3000 + 10;
int dp[maxn][maxn] , dp2[maxn][maxn] , par[maxn][maxn] ;
vector <int> cm ;
int ls[maxn][2*maxn] ;
std::vector<int> ucs(std::vector<int> A, std::vector<int> B) {
  vector <int> s  ,t ;int n = sz(A) , m = sz(B);
  s.pb(-1);
t.pb(-1);
vector <int> cm ; 
rep(i ,1 ,n){
  s.pb(A[i-1]);
  cm.pb(A[i-1]) ;
}
rep(j , 1 , m){
  t.pb(B[j-1]) ;
  cm.pb(B[j-1]);
}
sort(all(cm));
cm.resize(unique(all(cm)) - cm.begin()) ;
rep(i ,1 , n){
  int x= lower_bound(all(cm) , s[i]) - cm.begin() ;
  s[i] = x;   
}
rep(i , 1, m){
  int x = lower_bound(all(cm) , t[i]) - cm.begin() ;
  t[i] = x; 
}
rep(i ,1 ,n)rep(j ,1 ,m){
  dp[i][j] = dp[i-1][j] ;par[i][j] = 1; 
  if(dp[i][j] < dp[i][j-1]){
    dp[i][j] = dp[i][j-1] ;
    par[i][j]  = 2; 
  }
  if(s[i] == t[j] && dp[i][j] < dp[i-1][j-1]+1){
    dp[i][j] = dp[i-1][j-1]+1 ;
    par[i][j] = 3; 
  }
}
vector <int> l ;
int x = n , y = m ;
while(x != 0 && y!=0){
  if(par[x][y] == 3){
    l.pb(s[x] );
    x--;
    y--;
    continue ;
  }
  if(par[x][y] == 2){
    y--;
  }else{
    x--;
  }
}
l.pb(-1);
reverse(all(l));
  int X =sz(l)-1 ;
  rep(i ,1 ,X){
    rep(j , 0 ,sz(cm)-1){
      ls[i][j] = ls[i-1][j];
    }
    ls[i][l[i]] = i; 
  }
  per(i , n+1 ,1){
    per(j , m+1 ,1){
      if(i == n+1 || j == m+1){
        dp2[i][j] = X+1;
        continue ;
      }
      dp2[i][j] = min(dp2[i][j+1] , dp2[i+1][j]);
      if(s[i] == t[j]){
        if(dp2[i+1][j+1] == 0){
          dp2[i][j] = 0;
          continue ;
        }
        dp2[i][j] = min(dp2[i][j] , ls[dp2[i+1][j+1]-1][s[i]]);
      }
    }
  }
  if(dp2[1][1] > 0){
    vector <int> vec ;
    rep(i ,1, X){
      vec.pb(cm[l[i]]) ;
    }
    return vec ;
  }
  vector <int> vec ;
  vec.pb(-1);
  return vec ;
}

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