Submission #1221493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221493		nibert	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	171 ms	12272 KiB

hieroglyphs

#include <vector>
#include <queue>
#include <set>
#include <map>
#include <iostream>
using namespace std;

const int max_value = 200001 ;
bool is_sequence(const vector<int>&a , const vector<int>&b) {
    int j = 0;
    int m = b.size();
    for(int x : a) {
        if(j < m && b[j] == x) {
            j++;
        }
        
    }
    return j == m;
}
vector <int> coordinate_compression(vector <int> &arr){
    set<int> unique_values(arr.begin(), arr.end());
    map<int, int> mapping;
    int idx = 0;
    for(int val : unique_values) {
        mapping[val] = idx++;
    } 
    vector <int> compressed;
    for(int val : arr) {
        compressed.push_back(mapping[val]);
    }
    return compressed;
}
vector <int> get_subsequences (vector<int> A, vector<int> B) {
    int N = A.size(), M = B.size();
    vector<int> occurances_a(max_value, 0) , occurances_b(max_value,0);
    for(int x : A) {
        occurances_a[x]++;
    } 
    for(int y : B) {
        occurances_b[y]++;
    }
    vector<int> UCS;
    for(int x : A) {
        if(occurances_b[x]) {
            UCS.push_back(x);
        }
    }
    return UCS;
}
   
vector<int> ucs(vector<int> A, vector<int>B) {
    A = coordinate_compression(A);
    B = coordinate_compression(B);
    vector<int> sequences = get_subsequences(A,B);
    return is_sequence(A, sequences) && is_sequence(B,sequences) ? sequences : vector<int> {-1};
}

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