Submission #1153851

#TimeUsernameProblemLanguageResultExecution timeMemory
1153851yhkhooVlak (COCI20_vlak)C++20
0 / 70
8 ms13128 KiB
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define fi first
#define se second

const int MAXN = 200000;
int n, m;
string a[MAXN];
string b[MAXN];

unordered_map<string, bool> memo;

bool dp(string x){
    if(memo.count(x)){
        return memo[x];
    }
    bool eturn = x.length() % 2;
    bool ret;
    if(eturn){
        ret = 0;
        for(char i='a'; i<='z'; i++){
            string tmp = x+i;
            auto nx = lower_bound(b, b+n, tmp);
            if(nx == b+n || nx->length() <= x.length() || (*nx)[x.length()+1] != i || !(nx->starts_with(tmp))){
                //cerr << "no " + tmp << '\n';
                continue;
            }
            //cerr << "yes " + tmp << '\n';
            if(dp(tmp)){
                ret = 1;
                break;
            }
        }
    }
    else{
        ret = 1;
        for(char i='a'; i<='z'; i++){
            string tmp = x+i;
            auto nx = lower_bound(a, a+n, tmp);
            if(nx == a+n || nx->length() <= x.length() || (*nx)[x.length()+1] != i || !(nx->starts_with(tmp))){
                //cerr << "no " + tmp << '\n';
                continue;
            }
            //cerr << "yes " + tmp << '\n';
            if((!dp(tmp))){
                ret = 0;
                break;
            }
        }
    }
    memo[x] = ret;
    return ret;
}

int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    cin >> m;
    for(int i=0; i<m; i++){
        cin >> b[i];
    }
    sort(a, a+n);
    sort(b, b+n);
    if(dp("") == 0){
        cout << "Nina";
    }
    else{
        cout << "Emilija";
    }
    /*for(auto i: memo){
        cerr << i.fi << ' ' << i.se << '\n';
    }*/
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...