Submission #1135780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135780		shoeib	Vlak (COCI20_vlak)	C++20	30 / 70	10 ms	12872 KiB

Main

// Author: Muhammed Khaled Shoeib

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
//....................................................
// struct to speed-up the unordered data structures like map/set.
struct hash_function // unordered + modified hash >> ordered
{   static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM); } };
//....................................................
template < typename T, typename Compare = less < T > > // O(logn)
using ordered_set = tree < T, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;
// less_equal:    asc.  not_unique, st.order_of_key(k) --> no. of items < k,  less: unique
// greater_equal: desc. not_unique, st.order_of_key(k) --> no. of items > k,  greater: unique
// *st.find_by_order(k) --> st[k] (Zero-indexed)
// less_equal (u can't erase here!) == multi-set
template < typename T > using maxpq = priority_queue < T >;
template < typename T > using minpq = priority_queue < T, vector< T >, greater< T > >;
//....................................................
#define     boost                  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define     precision(a)           cout << fixed << setprecision(a)
#define     alo                    cout << "alooooooooooo!" << endl
#define     YES                    cout << "YES" << endl
#define     Yes                    cout << "Yes" << endl
#define     yes                    cout << "yes" << endl
#define     NO                     cout << "NO" << endl
#define     No                     cout << "No" << endl
#define     no                     cout << "no" << endl
#define     ne                     cout << -1 << endl
#define     endl                   "\n"
#define     mem(mat, val)          memset(mat, val, sizeof(mat))
#define     ones(x)                __builtin_popcountll(x)
#define     msb(x)                 63ll - __builtin_clzll(x)
#define     lsb(x)                 __builtin_ffsll(x) - 1ll
//....................................................
#define     all(x)                 x.begin(), x.end()
#define     rall(x)                x.rbegin(),x.rend()
#define ceil_(a, b) (((ll)(a) + (ll)(b - 1)) / (ll)(b)) // up
#define floor_(a, b) (a / b) // down
#define round_(a, b) ((a + (b / 2ll)) / b) // nearest
//....................................................
// using ll  = int;                                                                     // take care of this shit!
using ll  = long long;
using i64 = long long; using i32 = int;
using ld  = long double;  using ull = unsigned long long;  using lli = long long int;
//......................................................
ll gcd_(ll x, ll y) { return y ? gcd_(y, x % y) : x; } // O(log(min(x, y)))
ll lcm_(ll a, ll b) { ll g = gcd_(a, b); return (a * b) / g; }
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define getrand(l, r) uniform_int_distribution<long long>(l, r)(rng)
//......................................................
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dx_diag[4] = { 1, 1, -1, -1 }, dy_diag[4] = { 1, -1, -1, 1 };
int dx_all[8] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy_all[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dx_knight[8] = {2, 2, 1, 1, -2, -2, -1, -1}, dy_knight[8] = {1, -1, 2, -2, 1, -1, 2, -2};
const ld  pi  = 3.141592653589793238462643383279; // acos(-1)
const ld eps = 1e-9;
const ll inf = (ll)INT32_MAX; // 2e9
const ll oo = (ll)1e15;       // 1e15 (may cause OF in DP, Binary Search, ...)
const ll OO = (ll)INT64_MAX;  // 9e18
const ll mod = (ll)1e9 + 7; // 1e9 + 7, 998244353
//..................................................... // string(len, char);
/*
 * think twice, code once.
 * think of different approaches to tackle a problem, write them down.
 * think of different views of the problem, don't look from only one side.
 * don't get stuck in one approach/problem.
 * common mistakes: line 48, overflow (sum of many numbers), corner cases, over/under count, infinite loops,
 * TLE, MLE (int instead of ll, using memset, Recursive DP, ...), RTE (out of bounds indexing), ....
 */
///____________________________________________ Shoeib __________________________________________________________


/*              Trie (Prefix Tree)              */
// usefull when dealing with a lot of strings (we can move over all strings in the same time),
// efficient insertion, deletion, counting, search for specific property, ...
// the time complexity of all operations is O(n), where n is the length of the string being processed.
// if MLE --> remove useless variables.
// try to draw on a paper, and see information stored in each node.

// ....................

const ll mx_sz = 26;
const char _ref = 'a'; // 'a', 'A', '0'

// ....................

struct Trie
{
    struct Node
    {
        Node *ch[mx_sz];
        ll freq, end;
        Node() { mem(ch, 0); freq = end = 0; }
    };

    Node *root;
    Trie() { root = new Node(); }

    void insert(const string &s) // insert a new string
    {
        Node *curr = root;
        for(const auto &c : s)
        {
            ll idx = (ll)(c - _ref);
            if(!curr->ch[idx]) curr->ch[idx] = new Node();
            curr = curr->ch[idx];
            curr->freq++;
        }
        curr->end++;
    }

    void erase(const string &s, ll depth, Node *curr) // erase a string
    {
        if(depth == (ll)s.size()) { curr->end--; return; }

        ll idx = (ll)(s[depth] - _ref);

        erase(s, depth + 1, curr->ch[idx]);

        curr->ch[idx]->freq--;
        if(!curr->ch[idx]->freq)
        {
            delete curr->ch[idx];
            curr->ch[idx] = nullptr;
        }
    }
    void erase(const string &s) { if(count(s)) erase(s, 0, root); }

    ll count(const string &s) // count exact string
    {
        Node *curr = root;
        for(const auto &c : s)
        {
            ll idx = (ll)(c - _ref);
            if(!curr->ch[idx]) return 0;
            curr = curr->ch[idx];
        }
        return curr->end;
    }

    ll count_prefix(const string &s) // count prefix of the string
    {
        Node *curr = root;
        for(const auto &c : s)
        {
            ll idx = (ll)(c - _ref);
            if(!curr->ch[idx]) return 0;
            curr = curr->ch[idx];
        }
        return curr->freq;
    }

    // more methods ...

};

// ....................

void solve()
{

    ll n; cin >> n;
    set < string > a;
    while(n--)
    {
        string s; cin >> s;
        a.insert(s);
    }

    ll m; cin >> m;
    set < string > b;
    while(m--)
    {
        string s; cin >> s;
        b.insert(s);
    }


    Trie trie = Trie();
    for(const auto &i : b) trie.insert(i);


    ll ans = 0;
    for(const auto &j : a)
    {
        string s = j;
        ll n = (ll)s.size();

        ll i = 0, last = -1, good = 1;
        string tmp = "";
        for(ll i = 0; i < n; i++)
        {
            tmp += s[i];
            if(i % 2 == 0)
            {
                last = trie.count_prefix(tmp);
                if(!last)
                {
                    ans = 1;
                    break;
                }
            }
            else
            {
                if(last - trie.count_prefix(tmp))
                {
                    good = 0;
                    break;
                }
            }
        }
        if(good && !ans && n % 2 && !trie.count_prefix(tmp)) ans = 1;
    }

    cout << (ans ? "Nina" : "Emilija") << endl;





    return;
}




signed main()
{
    boost;

//    freopen("assessment.in", "r", stdin);
//    freopen("output.txt", "w", stdout);

//    precision(15);

    i32 _ = 1; //cin >> _;
//    cout.flush();
    while(_--) solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10