Submission #1204343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204343		perekopskad	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	1095 ms	144036 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)
#define pii pair <ll, ll>
#define ff first 
#define ss second 
#define el '\n'
#define pb push_back
#define mkp make_pair

ll const N = 3e3 + 10;

void chmax(ll &a, ll b) {
    a = max(a, b);
}

pii dp[N][N];
ll mx[N][N];
vector <ll> pos[N];

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

    fr(i, 1, n) {
        fr(j, 1, m) {
            dp[i][j] = max(dp[i][j], mkp(dp[i - 1][j].ff, 1ll));
            dp[i][j] = max(dp[i][j], mkp(dp[i][j - 1].ff, 2ll));
            if(A[i - 1] == B[j - 1])
                dp[i][j] = max(dp[i][j], mkp(dp[i - 1][j - 1].ff + 1, 3ll));
        }
    }

    ll i = n, j = m;
    vector <int> lcs;

    while(i && j) {
        if(dp[i][j].ss == 1) {
            i--;
        }
        else if(dp[i][j].ss == 2) {
            j--;
        }
        else {
            lcs.pb(A[i - 1]);
            i--;
            j--;
        }
    }

    reverse(lcs.begin(), lcs.end());
    for(int i = 0; i < lcs.size(); i++)
        pos[lcs[i]].pb(i + 1);

    fr(i, 1, n) {
        fr(j, 1, m) {
            chmax(mx[i][j], mx[i - 1][j]);
            chmax(mx[i][j], mx[i][j - 1]);
            if(A[i - 1] != B[j - 1])
                continue;
            
            ll x = mx[i - 1][j - 1];
            auto it = upper_bound(pos[A[i - 1]].begin(), pos[A[i - 1]].end(), x);
            if(it == pos[A[i - 1]].end())
                return {-1};

            chmax(mx[i][j], *it);
        }
    }
    return lcs;
}

• 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