Submission #1254762

#TimeUsernameProblemLanguageResultExecution timeMemory
1254762testaccountHieroglyphs (IOI24_hieroglyphs)C++20
14 / 100
1095 ms131652 KiB
#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 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...