제출 #1206387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206387		hihihahaa	상형문자열 (IOI24_hieroglyphs)	C++20	16 / 100	596 ms	610008 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];
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> ucs(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 < 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();
}
/*
signed main() {
    vector<int> sample_1 = ucs({0, 0, 1, 0, 1, 2}, {2, 0, 1, 0, 2});
    vector<int> sample_2 = ucs({0, 1, 0}, {1, 0, 1});
    for (auto i: sample_2) cout << i << " "; cout << "\n";
}
*/

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