oj.uz

Submission #529695

# Submission time Handle Problem Language Result Execution time Memory
529695 2022-02-23T13:05:24 Z mmonteiro Vlak (COCI20_vlak) C++17
70 / 70
 12 ms 11340 KB 
#include "bits/stdc++.h"

/*
 * Author: Matheus Monteiro
 */

using namespace std;

#define _ << " , " <<
#define bug(x) cout << #x << "  >>>>>>>  " << x << endl;

// #define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vii vector<ii>
#define LSOne(S) ((S) & (-S))
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int MAX = 300010; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9;  //10^-9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Trie {
    int trie[MAX][26], next_vertex = 1;
    void add(string &s) {
        int r = 0;
        for(char &c : s) {
            if(!trie[r][c - 'a']) trie[r][c - 'a'] = next_vertex++;
            r = trie[r][c - 'a'];
        }
    }
    int go(int node, int i) {
        return trie[node][i];
    }
    void dfs(int r) {
        cout << r << '\n';
        for(int i = 0; i < 26; ++i) {
            if(go(r, i)) {
                cout << char(i + 'a') << ' ' << go(r, i) << '\n';
                dfs(go(r, i));
            }
        }
    }
} nina, emi;

int n, m;
int dp[MAX][2], seen[MAX][2];

int grundy(int node_nina, int turn, int node_emi) {
    if(!node_nina and node_emi or !node_emi and node_nina)
        return 0;

    if(seen[node_nina][turn]) return dp[node_nina][turn];

    set<int> S;

    for(int i = 0; i < 26; ++i) {
        int new_nin_nod;
        int new_emi_nod;

        if(!turn) { // nina's turn
            new_nin_nod = nina.go(node_nina, i);
            if(new_nin_nod) {
                new_emi_nod = emi.go(node_emi, i);
                S.insert(grundy(new_nin_nod, turn ^ 1, new_emi_nod));
            }
        } else { // emi's turn
            new_emi_nod = emi.go(node_emi, i);
            if(new_emi_nod) {
                new_nin_nod = nina.go(node_nina, i);
                S.insert(grundy(new_nin_nod, turn ^ 1, new_emi_nod));
            }
        }
    }

    int mex = 0;
    while(S.count(mex)) ++mex;

    seen[node_nina][turn] = 1;
    return dp[node_nina][turn] = mex;
}

void solve() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        nina.add(s);
    }
    cin >> m;
    for(int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        emi.add(s);
    }

    // nina.dfs(0);
    // cout << endl;
    // emi.dfs(0);

    int flag = grundy(0, 0, 0);

    cout << (flag ? "Nina" : "Emilija") << '\n';
}

int32_t main() {

	fastio;
	int t = 1;
	//cin >> t;
	for(int caso = 1; caso <= t; ++caso) {
		//cout << "Case #" << caso << ": ";
		solve();
	}

	return 0;
}

/*
Before submit:
	Check the corners cases
	Check solution restrictions

For implementation solutions:
	Check the flow of the variables

For intervals problems:
	Think about two pointers

For complete search:
	Think about cuts

If you get WA:
	Reread your code looking for stupid typos
	Try various manual testcases 
	Recheck the correctness of your algorithm
	Reread the statement
	Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
	Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
	Change the coder (if you're with a team)
	Give up. You may have other tasks to solve.
*/

Compilation message

Main.cpp: In function 'int grundy(int, int, int)':
Main.cpp:58:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |     if(!node_nina and node_emi or !node_emi and node_nina)
      |        ~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10572 KB Output is correct
2 Correct 10 ms 9932 KB Output is correct
3 Correct 10 ms 9440 KB Output is correct
4 Correct 12 ms 10396 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10780 KB Output is correct
2 Correct 11 ms 11340 KB Output is correct
3 Correct 10 ms 10404 KB Output is correct
4 Correct 10 ms 10520 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10188 KB Output is correct
2 Correct 12 ms 9932 KB Output is correct
3 Correct 11 ms 10244 KB Output is correct
4 Correct 12 ms 10948 KB Output is correct