oj.uz

답안 #1079078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1079078 2024-08-28T10:27:16 Z boris_mihov Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 846 ms 128984 KB 
#include <unordered_map>
#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;
        }

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

    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);
    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::unordered_map <int, 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.value1]++;
        }

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

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

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8280 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 4 ms 8284 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 846 ms 128984 KB Output is correct
2 Correct 826 ms 127152 KB Output is correct
3 Correct 76 ms 46416 KB Output is correct
4 Correct 93 ms 46388 KB Output is correct
5 Incorrect 428 ms 81292 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 14900 KB Output is correct
2 Correct 27 ms 13772 KB Output is correct
3 Correct 31 ms 14364 KB Output is correct
4 Correct 26 ms 13456 KB Output is correct
5 Correct 28 ms 13260 KB Output is correct
6 Correct 36 ms 14024 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8280 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 4 ms 8284 KB Output is correct
8 Correct 846 ms 128984 KB Output is correct
9 Correct 826 ms 127152 KB Output is correct
10 Correct 76 ms 46416 KB Output is correct
11 Correct 93 ms 46388 KB Output is correct
12 Incorrect 428 ms 81292 KB Output isn't correct
13 Halted 0 ms 0 KB -