Submission #1213013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213013		ay136416	Vlak (COCI20_vlak)	Java	70 / 70	169 ms	33224 KiB

Main

/// read all the words into a trie, marking who has what word
// minimax like strategy
// generate test case!!!!
import java.util.Scanner;
import java.util.StringJoiner;

class Main {
    static class Trie {
        TrieNode head; // does it belong to nina, but we don't say she has moves if it's a leaf node 
        /*public void add(char[] s, boolean belongsToNina) {
            TrieNode cur = head;
            int i = 0;
            
            while (i < s.length) {
                //System.out.println((int) s[i]);
                if (belongsToNina) {
                    cur.num_ninaswords_on_or_below++;
                } else {
                    cur.num_emiljaswords_on_or_below++;
                }
                if (cur.leaves[s[i]-'a'] == null) {
                    cur.leaves[s[i]-'a'] = new TrieNode();
                }
                cur = cur.leaves[s[i]-'a'];
                
                
                i++;
            }
            /*if (belongsToNina) {
                cur.num_ninaswords_on_or_below++;
            } else {
                cur.num_emiljaswords_on_or_below++;
            }
            cur.isTerminal=true;
            /*if (belongsToNina) {
                cur.num_ninaswords_on_or_below++;
            } else {
                cur.num_emiljaswords_on_or_below++;
            }
        }*/
        public Trie() {
            head = new TrieNode();
        }
        public String toString() {
            return this.head.toString();
        }
    }
    static class TrieNode {
        long num_ninaswords_on_or_below;
        long num_emiljaswords_on_or_below;
        boolean isTerminal;
        TrieNode[] leaves;
        public TrieNode() {
            num_emiljaswords_on_or_below=0;
            num_ninaswords_on_or_below=0;
            isTerminal=false;
            //this.belongsToNina = belongsToNina;
            leaves = new TrieNode[28];
        }
        public void add(char[] s, int pos, boolean belongsToNina) {
            if (pos==s.length) return;
            if (belongsToNina) {
                this.num_ninaswords_on_or_below++;
            } else {
                this.num_emiljaswords_on_or_below++;
            }
            if (this.leaves[s[pos]-'a'] == null) {
                this.leaves[s[pos]-'a'] = new TrieNode();
            }
            this.leaves[s[pos]-'a'].add(s, pos+1, belongsToNina);
        }
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("<TrieNode nina="+num_ninaswords_on_or_below+" emilja="+num_emiljaswords_on_or_below+" leaves=[");
            StringJoiner sj = new StringJoiner(", ");
            for (int i = 0; i<26; i++) {
                if (leaves[i]!=null) {
                    sj.add((char) (i+'a') + ": " + leaves[i].toString());
                }
            }
            sb.append(sj.toString());
            sb.append("]>");
            return new String(sb);
        }
        public boolean hasNoChildren() {
            for (int i = 0; i<leaves.length; i++) {
                if (leaves[i] != null) return false;
            }
            return true;
        }
    }
    public static void main(String[] args) {
        //System.err.println("I am ready");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Trie trie = new Trie();
        for (int i = 0; i<n; i++) {
            trie.head.add(sc.next().toCharArray(),0, true);
        }
        int m = sc.nextInt();
        for (int i = 0; i<m; i++) {
            trie.head.add(sc.next().toCharArray(),0, false);
        }
        sc.close();
       // System.out.println("THIS IS MY TRIE: " + trie + "\n\n\n");
        /*for (int i = 0; i<trie.head.leaves.length; i++) {
            if (trie.head.leaves[i] != null) {
                if (!minimax(trie.head.leaves[i], false)) ans=true;
            }
        }*/
        boolean ans = minimax(trie.head, true);
        System.out.println(ans ? "Nina" : "Emilija");
    }

    public static boolean minimax(TrieNode node, boolean maximizingPlayer) { // returns whether i win
        //if (node==null) return false;
        if (maximizingPlayer && node.num_ninaswords_on_or_below == 0) return false;
        if (!maximizingPlayer && node.num_emiljaswords_on_or_below == 0) return false;
        /*if (maximizingPlayer) {
            boolean can=false;
            for (int i = 0; i<node.leaves.length; i++) {
                if (node.leaves[i] != null && node.leaves[i].num_ninaswords_on_or_below > 0) can=true;
            }
            //if (!can) return false;
        } else {
            boolean can=false;
            for (int i = 0; i<node.leaves.length; i++) {
                if (node.leaves[i] != null && node.leaves[i].num_emiljaswords_on_or_below > 0) can=true;
            }
            //if (!can) return false;
        }*/
        

        for (int i = 0; i<node.leaves.length; i++) {
            if (node.leaves[i] != null) {
                if (!minimax(node.leaves[i], !maximizingPlayer)) return true;
            }
        }
        return false;
        //}
        //if (!maximizingPlayer && node.num_emiljaswords_on_or_below == 0) return false;
        /*boolean canMakeMove = false;
        for (int i = 0; i<node.leaves.length; i++) {
            if (node.leaves[i] != null) {
                if (
                    (maximizingPlayer && node.leaves[i].num_ninaswords_below>0)
                    ||(!maximizingPlayer && node.leaves[i].num_emiljaswords_below>0)) 
                    canMakeMove=true;
            }
        }
        if (!canMakeMove) return false;*/
    }

}

• 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