Submission #1153822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153822		yhkhoo	Vlak (COCI20_vlak)	C++20	10 / 70	9 ms	13128 KiB

Main

#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 && 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 && (!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";
    }
    return 0;
}

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