Submission #1153860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153860		yhkhoo	Vlak (COCI20_vlak)	C++20	70 / 70	8 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+m, tmp);
            if(nx == b+m || nx->length() <= x.length() || (*nx)[x.length()] != i || !nx->starts_with(x)){
                //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()] != i || !nx->starts_with(x)){
                //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+m);
    if(dp("") == 0){
        cout << "Nina";
    }
    else{
        cout << "Emilija";
    }
    /*for(auto i: memo){
        cerr << i.fi << ' ' << i.se << '\n';
    }*/
    return 0;
}

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