Submission #1207077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207077		hihihahaa	Hieroglyphs (IOI24_hieroglyphs)	C++20	44 / 100	862 ms	783548 KiB

hieroglyphs

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

int n, m, cnt[cap], sub_cnt[cap], min_id[cap], max_id[cap];
int mark_a[cap], mark_b[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[1000][cap/2+1], pre_block_b[cap/2+1][1000];
vector<int> a, b;

void setup(vector<int> A, vector<int> B) {
    a = A; b = B;
    n = a.size(), m = b.size();
    // block_size = sqrt(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]]--;
    }
}

int check(int la, int ra, int lb, int rb) {
    if (la >= ra || lb >= rb) return -1;
    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> find_maximal_subsequence(vector<int> A, vector<int> B) {
    setup(A, B);
    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;
}

int find_lower(int x, vector<pair<int, int>>& A) {
    int l = -1, r = A.size();
    while (r - l > 1) {
        int mid = (l+r)/2;
        if (A[mid].second > x) r = mid;
        else l = mid;
    }
    return l;
}

int find_upper(int x, vector<pair<int, int>>& A) {
    int l = -1, r = A.size();
    while (r - l > 1) {
        int mid = (l+r)/2;
        if (A[mid].second < x) l = mid;
        else r = mid;
    }
    return r;
}

int find(int x, vector<pair<int, int>>& A) {
    // if guaranteed exists
    return find_lower(x, A);
}

vector<int> ucs(vector<int> A, vector<int> B) {
    vector<int> X = find_maximal_subsequence(A, B);
    
    // /* debug */ for (auto i: X) cout << i << " "; 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;
    }
    
    // modify mark_a, mark_b
    for (int i = 0; i < cap; i++) mark_a[i] = mark_b[i] = -1;
    
    // check inversions
    if (!X.empty()) {
        vector<pair<int, int>> match(X.size());
        
        int n = A.size(), m = B.size();
        for (int i = 0, i_x = 0; i < n && i_x < X.size(); i++) {
            if (X[i_x] == A[i]) {
                mark_a[i] = i_x;
                match[i_x].first = i;
                i_x++;
            }
        }
        for (int j = 0, i_x = 0; j < m && i_x < X.size(); j++) {
            if (X[i_x] == B[j]) {
                mark_b[j] = i_x;
                match[i_x].second = j;
                i_x++;
            }
        }
        for (int i = 0; i < cap; i++) {
            min_id[i] = inf; max_id[i] = -inf;
        }
        for (int i = 0; i < n; i++) if (mark_a[i] == -1) {
            min_id[A[i]] = min(min_id[A[i]], i);
            max_id[A[i]] = max(max_id[A[i]], i);
        }
        vector<pair<int, int>> AA, BB;
        for (int i = 0; i < n; i++) if (mark_a[i] != -1) AA.push_back({A[i], i});
        for (int j = 0; j < m; j++) if (mark_b[j] == -1) BB.push_back({B[j], j});
        
        if (!AA.empty() && !BB.empty()) {
            // find tuples for each queries
            vector<pair<pair<int, int>, pair<int, int>>> query;
            for (auto p: match) {
                int la, ra, lb, rb;
                int pivot_a = p.first, pivot_b = p.second;
                int l = min_id[A[pivot_a]];
                // /* debug */ cout << min_id[A[pivot_a]] << "\n";
                if (l < pivot_a) {
                    la = find_upper(l, AA);
                    ra = find(pivot_a, AA);
                    lb = find_upper(pivot_b, BB);
                    rb = BB.size();
                    query.push_back({{la, ra}, {lb, rb}});
                    // /* debug */ cout << la << " " << ra << " || " << lb << " " << rb << "\n";
                }
                int r = max_id[A[pivot_a]];
                if (r > pivot_a) {
                    la = find(pivot_a, AA) + 1;
                    ra = find_lower(r, AA) + 1;
                    lb = 0;
                    rb = find_lower(pivot_b, BB) + 1;
                    query.push_back({{la, ra}, {lb, rb}});
                    // /* debug */ cout << la << " " << ra << " || " << lb << " " << rb << "\n";
                }
            }
            
            // process queries
            vector<int> AA_copy, BB_copy;
            for (auto p: AA) AA_copy.push_back(p.first);
            for (auto p: BB) BB_copy.push_back(p.first);
            setup(AA_copy, BB_copy);
            for (auto p: query) {
                int la = p.first.first, ra = p.first.second,
                lb = p.second.first, rb = p.second.second;
                if (check(la, ra, lb, rb) != -1) stt = false;
            }
        }
    }
    if (stt) return X;
    return {-1};
}

/*
signed main() {
    int l, r; cin >> l >> r;
    
    vector<pair<vector<int>, vector<int>>> sample (10, {vector<int>(), vector<int>()});
    sample[1] = {{0, 0, 1, 0, 1, 2}, {2, 0, 1, 0, 2}};
    sample[2] = {{0, 0, 2}, {1, 1}};
    sample[3] = {{0, 1, 0}, {1, 0, 1}};
    sample[4] = {{1, 0, 1, 0, 1, 0, 1}, {0, 1, 0, 1, 0, 1, 0}};
    sample[5] = {{1, 0, 2, 0}, {1, 0, 2, 1}};
    sample[6] = {{1, 2, 3, 0, 1, 2}, {1, 2, 1, 0, 1}};
    for (int i = l; i <= r; i++) {
        cout << "Case #" << i << ": " << "\n";
        vector<int> UCS = ucs(sample[i].first, sample[i].second);
        for (auto j: UCS) cout << j << " "; cout << "\n";
    } 
}
*/

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