Submission #1079075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079075		boris_mihov	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	36 ms	41816 KiB

selling_rna

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MOD1 = 1000003013;
const int MOD2 = 1000003241;
const int BASE = 5;

int n, q;
int decode[256];
// int base1[MAXN];
// int base2[MAXN];
struct String
{
    std::string value;
    struct Hash
    {
        llong value1, value2;
        Hash()
        {
            value1 = value2 = 0;
        }
        
        void push(char letter)
        {
            value1 *= BASE;
            // value2 *= BASE;
            value1 += decode[letter];
            // value2 += decode[letter];
            value1 %= MOD1;
            // value2 %= MOD2;
        }

        friend bool operator < (const Hash &a, const Hash &b)
        {
            return a.value1 < b.value1 || (a.value1 == b.value1 && a.value2 < b.value2);
        }

        friend bool operator == (const Hash &a, const Hash &b)
        {
            return a.value1 == b.value1 && a.value2 == b.value2;
        }
    };

    std::vector <Hash> prefix;
    void initalize()
    {
        Hash curr;
        prefix.reserve(value.size());
        for (int i = 0 ; i < value.size() ; ++i)
        {
            curr.push(value[i]);
            prefix.push_back(curr);
        }
    }

    friend bool operator < (const String &a, const String &b)
    {
        int l = -1, r = std::max(a.value.size(), b.value.size()), mid;
        while (l < r - 1)
        {
            mid = l + r >> 1;
            if (a.prefix[mid] == b.prefix[mid]) l = mid;
            else r = mid;
        }

        if (r == std::max(a.value.size(), b.value.size()))
        {
            return a.value.size() < b.value.size();
        }

        if (a.value[r] < b.value[r]) return true;
        return false;
    }

    bool isPrefix(const String &a)
    {
        if (a.value.size() <= value.size() && a.prefix.back() == prefix[a.value.size() - 1]) return true;
        return false;
    }
};

String s[MAXN];
struct Query
{
    char type;
    String::Hash hash;
    int idx;
};

int output[MAXN];
std::vector <Query> queries[MAXN];

void solve()
{
    std::sort(s + 1, s + 1 + n);
    return;
    
    for (int i = 1 ; i <= q ; ++i)
    {
        String p, q;
        std::cin >> p.value >> q.value;
        std::reverse(q.value.begin(), q.value.end());
        p.initalize(); q.initalize();
        
        int start, end;
        {
            int l = 0, r = n + 1, mid;
            while (l < r - 1)
            {
                mid = l + r >> 1;
                if (s[mid].isPrefix(p))
                {
                    r = mid;
                    continue;
                }

                if (s[mid] < p) l = mid;
                else r = mid;
            }
            
            start = r;
        }

        {
            int l = 0, r = n + 1, mid;
            while (l < r - 1)
            {
                mid = l + r >> 1;
                // std::cout << "here: " << p.value << ' ' << s[mid].value << ' ' << l << ' ' << r << ' ' << mid << ' ' << (p.value < s[mid].value) << '\n';
                if (s[mid].isPrefix(p))
                {
                    l = mid;
                    continue;
                }

                if (s[mid] < p) l = mid;
                else r = mid;
            }
            
            end = l;
        }

        // std::cout << "start end: " << p.value << ' ' << start << ' ' << end << '\n';
        queries[start - 1].push_back({'-', q.prefix.back(), i});
        queries[end].push_back({'+', q.prefix.back(), i});
    }

    std::map <String::Hash, int> cnt;
    for (int i = 1 ; i <= n ; ++i)
    {
        String::Hash curr;
        for (int j = s[i].value.size() - 1; j >= 0 ; --j)
        {
            curr.push(s[i].value[j]);
            cnt[curr]++;
        }

        for (const auto &[type, h, idx] : queries[i])
        {
            if (type == '-') output[idx] -= cnt[h];
            else output[idx] += cnt[h];
        }
    }
}

void input()
{
    std::cin >> n >> q;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> s[i].value;
        s[i].initalize();
    }
}

void print()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << output[i] << '\n';
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

void initialize()
{
    decode['A'] = 1;
    decode['C'] = 2;
    decode['G'] = 3;
    decode['U'] = 4;

    // base1[0] = base2[0] = 1;
    // for (int i = 1 ; i < MAXN ; ++i)
    // {
    //     base1[i] = (1LL * base1[i - 1] * BASE) % MOD1;
    //     base2[i] = (1LL * base2[i - 1] * BASE) % MOD2;
    // }
}

int main()
{
    initialize();
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void String::Hash::push(char)':
selling_rna.cpp:33:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   33 |             value1 += decode[letter];
      |                              ^~~~~~
selling_rna.cpp: In member function 'void String::initalize()':
selling_rna.cpp:55:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 0 ; i < value.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'bool operator<(const String&, const String&)':
selling_rna.cpp:67:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |             mid = l + r >> 1;
      |                   ~~^~~
selling_rna.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   72 |         if (r == std::max(a.value.size(), b.value.size()))
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:116:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |                 mid = l + r >> 1;
      |                       ~~^~~
selling_rna.cpp:134:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  134 |                 mid = l + r >> 1;
      |                       ~~^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40