Submission #1206694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206694		hihihahaa	상형문자열 (IOI24_hieroglyphs)	C++20	19 / 100	972 ms	612312 KiB

hieroglyphs

#include <bits/stdc++.h>
using namespace std;
const int cap = 2e5+1;
const int half_cap = 500;

int n, m, block_size, cnt[cap], sub_cnt[cap];
vector<set<int>> find_floor_a (cap, set<int>()), find_ceil_a(cap, set<int>()), find_floor_b(cap, set<int>()), find_ceil_b(cap, set<int>());
pair<int, int> pre_block_a[half_cap][cap], pre_block_b[cap][half_cap];
vector<int> a, b;

int check(int la, int ra, int lb, int rb) {
    int LA = ceil((double)la/block_size)*block_size, LB = ceil((double)lb/block_size)*block_size,
    RA = floor((double)ra/block_size)*block_size, RB = floor((double)rb/block_size)*block_size;
    
    // /* debug */ cout << la << " " << ra << " " << lb << " " << rb << "\n";
    
    // check b to block a
    for (int i = LA/block_size; i < RA/block_size; i++) {
        pair<int, int> test = {pre_block_a[i][rb].first - pre_block_a[i][lb].first, pre_block_a[i][rb].second};
        if (test.first) return test.second;
    }
    // check a to block b
    for (int j = LB/block_size; j < RB/block_size; j++) {
        pair<int, int> test = {pre_block_b[ra][j].first - pre_block_b[la][j].first, pre_block_b[ra][j].second};
        if (test.first) return test.second;
    }
    if (LA > RA) LA = RA = la;
    if (LB > RB) LB = RB = lb;
    for (int i = la; i < LA; i++) cnt[a[i]]++;
    for (int i = RA; i < ra; i++) cnt[a[i]]++;
    int ans = -1;
    for (int j = lb; j < LB; j++) if (cnt[b[j]]) ans = b[j];
    for (int j = RB; j < rb; j++) if (cnt[b[j]]) ans = b[j];
    for (int i = la; i < LA; i++) cnt[a[i]]--;
    for (int i = RA; i < ra; i++) cnt[a[i]]--;
    
    return ans;
}

int find_ceil(int l, int r, int x, bool is_A) {
    if (is_A) {
        return -*find_ceil_a[x].upper_bound(-r);
    }
    return -*find_ceil_b[x].upper_bound(-r);
}

int find_floor(int l, int r, int x, bool is_A) {
    if (is_A) {
        return *find_floor_a[x].lower_bound(l);
    }
    return *find_floor_b[x].lower_bound(l);
}

vector<int> solve() {
    stack<int> ans;
    stack<pair<int, int>> S;
    S.push({-1, -1});
    pair<int, int> top = {n, m};
    while (!S.empty()) {
        pair<int, int> p = S.top();
        int la = p.first, lb = p.second, ra = top.first, rb = top.second;
        int x = check(la+1, ra, lb+1, rb);
        // /* debug */ cout << x << "\n";
        if (x == -1) {
            S.pop();
            if (!S.empty()){
                // x = a[la] = b[lb];
                int x = a[la];
                top = {find_ceil(la, ra, x, 1), find_ceil(lb, rb, x, 0)};
                ans.push(x);
            }
        } else {
            S.push({find_floor(la+1, ra, x, 1), find_floor(lb+1, rb, x, 0)});
        }
    }
    vector<int> out; while (!ans.empty()) {
        out.push_back(ans.top()); ans.pop();
    }
    return out;
}

vector<int> find_maximal_subsequence(vector<int> A, vector<int> B) {
    a = A; b = B;
    n = a.size(), m = b.size();
    // block_size = sqrt(n); 
    block_size = half_cap;
    assert(half_cap >= n/block_size);
    assert(half_cap >= m/block_size);
    
    // /* debug */ cout << "block_size: " << block_size << "\n";
    
    for (int i = 0; i < cap; i++) {
        find_floor_a[i].clear(); find_ceil_a[i].clear();
        find_floor_b[i].clear(); find_ceil_b[i].clear();
    }
    for (int i = 0; i < n; i++) {
        find_floor_a[a[i]].insert(i);
        find_ceil_a[a[i]].insert(-i);
    }
    for (int i = 0; i < m; i++) {
        find_floor_b[b[i]].insert(i);
        find_ceil_b[b[i]].insert(-i);
    }
    
    // pre-compute
    for (int i = 0; i < n/block_size; i++) {
        pre_block_a[i][0] = {0, 0};
        for (int i0 = 0; i0 < block_size; i0++) cnt[a[i*block_size + i0]]++;
        for (int j = 0; j < m; j++) {
            if (cnt[b[j]]) pre_block_a[i][j+1] = {pre_block_a[i][j].first+1, b[j]};
            else pre_block_a[i][j+1] = pre_block_a[i][j];
        }
        for (int i0 = 0; i0 < block_size; i0++) cnt[a[i*block_size + i0]]--;
    } 
    for (int j = 0; j < m/block_size; j++) {
        pre_block_b[0][j] = {0, 0};
        for (int j0 = 0; j0 < block_size; j0++) cnt[b[j*block_size + j0]]++;
        for (int i = 0; i < n; i++) {
            if (cnt[a[i]]) pre_block_b[i+1][j] = {pre_block_b[i][j].first+1, a[i]};
            else pre_block_b[i+1][j] = pre_block_b[i][j];
        }
        for (int j0 = 0; j0 < block_size; j0++) cnt[b[j*block_size + j0]]--;
    } 
    
    return solve();
}

vector<int> ucs(vector<int> A, vector<int> B) {
    vector<int> X = find_maximal_subsequence(A, B);
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());
    vector<int> Y = find_maximal_subsequence(A, B);
    reverse(Y.begin(), Y.end());
    
    // /* debug */ for (auto i: X) cout << i << " "; cout << "\n";
    // for (auto j: Y) cout << j << " "; cout << "\n";
    
    // check for duplicates between A\X and B\X
    bool stt = true;
    for (auto i: A) cnt[i]++;
    for (auto j: B) sub_cnt[j]++;
    for (int i = 0; i < cap; i++) cnt[i] = min(cnt[i], sub_cnt[i]);
    for (auto i: X) cnt[i]--;
    for (int i = 0; i < cap; i++) {
        if (cnt[i]) stt = false;
        cnt[i] = 0; sub_cnt[i] = 0;
    }
    // check X == Y 
    if (X.size() != Y.size()) stt = false;
    else for (int i = 0; i < X.size(); i++) if (X[i] != Y[i]) stt = false;
    if (stt) return X;
    return {-1};
}
/*
signed main() {
    vector<vector<int>> sample (10, vector<int>());
    sample[1] = ucs({0, 0, 1, 0, 1, 2}, {2, 0, 1, 0, 2});
    sample[2] = ucs({0, 0, 2}, {1, 1});
    sample[3] = ucs({0, 1, 0}, {1, 0, 1});
    sample[4] = ucs({1, 0, 1, 0, 1, 0, 1}, {0, 1, 0, 1, 0, 1, 0});
    int limit = 4;
    for (int i = 1; i <= limit; i++) {
        cout << "Case #" << i << ": " << "\n";
        for (auto j: sample[i]) cout << j << " "; cout << "\n";
    } 
}
*/

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