Submission #304914

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
304914	2020-09-22T07:47:16 Z	model_code	Counting Mushrooms (IOI20_mushrooms)	Java 11	100 / 100	1939 ms	98984 KB

mushrooms

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.Map.Entry;

/*
 * Full solution for task mushrooms
 *
 * Author: Mikhail Tikhomirov
 * (ported from C++ by Kian)
 */
public class mushrooms {

	private static void _assert(boolean cond) {
		if (!cond)
			throw new AssertionError();
	}

	private static int bool2int(boolean b) {
		return b ? 1 : 0;
	}
	private static boolean int2bool(int i) {
		return i != 0;
	}


	private int use_machine(int[] x) {
		return stub.use_machine(x);
	}

	private int use_machine(List<Integer> x) {
		int[] xa = new int[x.size()];
		for (int i = 0; i < xa.length; i++)
			xa[i] = x.get(i);
		return use_machine(xa);
	}

	private static class IterableComparator<T extends Comparable<T>> implements Comparator<Iterable<T>> {
		@Override
		public int compare(Iterable<T> a, Iterable<T> b) {
			Iterator<T> ita = a.iterator();
			Iterator<T> itb = b.iterator();
			while (ita.hasNext()) {
				if (!itb.hasNext())
					return 1;
				T itema = ita.next();
				T itemb = itb.next();
				int c = itema.compareTo(itemb);
				if (int2bool(c))
					return c;
			}
			return itb.hasNext() ? -1 : 0;
		}
	}

	private static class LIMap<T> extends TreeMap<List<Integer>, T> {
		static final long serialVersionUID = 1L;
		public LIMap(Object... initialValues) {
			super(new IterableComparator<>());
			IllegalArgumentException ex = new IllegalArgumentException("Args must be pairs of (List<Integer>, String)");
			if (initialValues.length % 2 != 0)
				throw ex;
			for (int i = 0; i < initialValues.length; i+=2) {
				if (!(initialValues[i] instanceof List))
					throw ex;
				@SuppressWarnings("unchecked")
				List<Integer> k = (List<Integer>)initialValues[i];
				@SuppressWarnings("unchecked")
				T v = (T)initialValues[i+1];
				this.put(k, v);
			}
		}
	}


	int[] labels;
	List<List<Integer>> lst;
	int K = 110;

	int ans;

	void label(int p, int z) {
		labels[p] = z;
		lst.get(z).add(p);
		if (!int2bool(z)) ++ans;
	}

	int p = 1;
	int z;
	List<Integer> toQ = new ArrayList<>();

	String subs(String s0, int mask) {
		char[] s = s0.toCharArray();
		for (int i = 0; i < s.length; i++){
			char c = s[i];
			if (c >= 'A' && c <= 'Z')
				s[i] = (char)('0' + ((mask >> (c - 'A')) & 1));
		}
		return new String(s);
	}

	int eval(final String s) {
		int ret = 0;
		for (int i = 0; i < s.length() - 1; i++)
			ret += bool2int(s.charAt(i) != s.charAt(i + 1));
		return ret;
	}

	int query(String s) {
		List<Integer> v = new ArrayList<>();
		int[] ptr = new int[2];
		for (char c: s.toCharArray()) {
			if (c == '0' || c == '1') {
				int d = (c - '0') ^ z;
				_assert(ptr[d] < lst.get(d).size());
				v.add(lst.get(d).get(ptr[d]++));
			} else {
				int l = c - 'A';
				v.add(toQ.get(l));
			}
		}
		return use_machine(v);
	}

	LIMap<String> prec1 = new LIMap<>(
		Arrays.asList(), "A0B0C0DE",
		Arrays.asList(1), "CED",
		Arrays.asList(2), "DBE0A",
		Arrays.asList(3), "CB0E0DA1",
		Arrays.asList(4), "D0A0E0CB1",
		Arrays.asList(5), "DBCE1",
		Arrays.asList(6), "CED"
	);

	LIMap<String> prec2 = new LIMap<>(
		Arrays.asList(), "ABCDE0",
		Arrays.asList(1), "B0",
		Arrays.asList(1, 1), "EADC",
		Arrays.asList(2), "CB0D",
		Arrays.asList(2, 1), "EADB",
		Arrays.asList(2, 2), "DAE0CB",
		Arrays.asList(3), "CB0D",
		Arrays.asList(3, 1), "EDB0",
		Arrays.asList(3, 2), "AED",
		Arrays.asList(3, 3), "ED",
		Arrays.asList(4), "B0",
		Arrays.asList(4, 1), "0EACD"
	);


	void magic(LIMap<String> m) {
		toQ.clear();
		for (int i = 0; i < 5; i++)
			toQ.add(p + i);
		List<Integer> seq = new ArrayList<>();
		Map<String, Integer> res = new TreeMap<>();
		while (m.containsKey(seq)) {
			String s = m.get(seq);
			int x = query(s);
			res.put(s, x);
			seq.add(x);
		}
		List<Integer> goodM = new ArrayList<>();
		for (int mask = 0; mask < 32; mask++) {
			boolean ok = true;
			for (Entry<String, Integer> w : res.entrySet())
				ok &= eval(subs(w.getKey(), mask)) == w.getValue();
			if (ok) goodM.add(mask);
		}
		_assert(goodM.size() == 1);
		int mask = goodM.get(0);
		for (int i = 0; i < 5; i++)
			label(p++, ((mask >> i) & 1) ^ z);
	}

	public int count_mushrooms(int n) {
		labels = new int[n];
		Arrays.fill(labels, -1);
		lst = new ArrayList<>();
		for (int i = 0; i<2; i++)
			lst.add(new ArrayList<>());
		p = 1;
		ans = 0;
		label(0, 0);
		while (p < n) {
			z = lst.get(0).size() > lst.get(1).size() ? 0 : 1;
			if (n - p < 5 || lst.get(z).size() >= K) {
				List<Integer> m = new ArrayList<>();
				int i = 0;
				while (p < n && i < lst.get(z).size()) {
					m.add(p++);
					m.add(lst.get(z).get(i++));
				}
				int x = use_machine(m);
				lst.get(z ^ (x & 1)).add(m.get(0));
				x = (x + 1) / 2;
				ans += (int2bool(z) ? x : i - x);
			} else magic(!lst.get(z ^ 1).isEmpty() && lst.get(z).size() >= 3 ? prec1 : prec2);
		}
		return ans;
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	114 ms	11748 KB	Output is correct
2	Correct	117 ms	11784 KB	Output is correct
3	Correct	119 ms	11600 KB	Output is correct
4	Correct	130 ms	11940 KB	Output is correct
5	Correct	208 ms	13696 KB	Output is correct
6	Correct	432 ms	22752 KB	Output is correct
7	Correct	1704 ms	84308 KB	Output is correct
8	Correct	1600 ms	83544 KB	Output is correct
9	Correct	1454 ms	69552 KB	Output is correct
10	Correct	1614 ms	85632 KB	Output is correct
11	Correct	1615 ms	83508 KB	Output is correct
12	Correct	1513 ms	89816 KB	Output is correct
13	Correct	1380 ms	80944 KB	Output is correct
14	Correct	780 ms	51900 KB	Output is correct
15	Correct	1656 ms	86396 KB	Output is correct
16	Correct	1695 ms	88796 KB	Output is correct
17	Correct	1004 ms	56376 KB	Output is correct
18	Correct	1437 ms	84284 KB	Output is correct
19	Correct	1380 ms	85148 KB	Output is correct
20	Correct	1680 ms	84440 KB	Output is correct
21	Correct	1691 ms	77476 KB	Output is correct
22	Correct	1665 ms	88820 KB	Output is correct
23	Correct	1508 ms	86764 KB	Output is correct
24	Correct	855 ms	53800 KB	Output is correct
25	Correct	1766 ms	86224 KB	Output is correct
26	Correct	1404 ms	80408 KB	Output is correct
27	Correct	1357 ms	83392 KB	Output is correct
28	Correct	1665 ms	90152 KB	Output is correct
29	Correct	1461 ms	86384 KB	Output is correct
30	Correct	1362 ms	85908 KB	Output is correct
31	Correct	1676 ms	86500 KB	Output is correct
32	Correct	1596 ms	82936 KB	Output is correct
33	Correct	1380 ms	87108 KB	Output is correct
34	Correct	1390 ms	73012 KB	Output is correct
35	Correct	1627 ms	87736 KB	Output is correct
36	Correct	1701 ms	91920 KB	Output is correct
37	Correct	1505 ms	78224 KB	Output is correct
38	Correct	1319 ms	84336 KB	Output is correct
39	Correct	1380 ms	79864 KB	Output is correct
40	Correct	1676 ms	83876 KB	Output is correct
41	Correct	1642 ms	77592 KB	Output is correct
42	Correct	1697 ms	73900 KB	Output is correct
43	Correct	1714 ms	91896 KB	Output is correct
44	Correct	1700 ms	75408 KB	Output is correct
45	Correct	1623 ms	68532 KB	Output is correct
46	Correct	1866 ms	86508 KB	Output is correct
47	Correct	1585 ms	86868 KB	Output is correct
48	Correct	1659 ms	85232 KB	Output is correct
49	Correct	1753 ms	91492 KB	Output is correct
50	Correct	1834 ms	91636 KB	Output is correct
51	Correct	1909 ms	79588 KB	Output is correct
52	Correct	1823 ms	98984 KB	Output is correct
53	Correct	1888 ms	98044 KB	Output is correct
54	Correct	1939 ms	97216 KB	Output is correct
55	Correct	1660 ms	80536 KB	Output is correct
56	Correct	1591 ms	82628 KB	Output is correct
57	Correct	1451 ms	84832 KB	Output is correct
58	Correct	1512 ms	87108 KB	Output is correct
59	Correct	1773 ms	86612 KB	Output is correct
60	Correct	1552 ms	85660 KB	Output is correct
61	Correct	1736 ms	92996 KB	Output is correct
62	Correct	124 ms	11624 KB	Output is correct
63	Correct	118 ms	11556 KB	Output is correct
64	Correct	123 ms	11548 KB	Output is correct
65	Correct	118 ms	11560 KB	Output is correct
66	Correct	123 ms	11660 KB	Output is correct
67	Correct	125 ms	11672 KB	Output is correct
68	Correct	123 ms	11640 KB	Output is correct
69	Correct	122 ms	11712 KB	Output is correct
70	Correct	125 ms	11632 KB	Output is correct
71	Correct	122 ms	11648 KB	Output is correct
72	Correct	123 ms	11760 KB	Output is correct
73	Correct	122 ms	11636 KB	Output is correct
74	Correct	127 ms	11672 KB	Output is correct
75	Correct	136 ms	11840 KB	Output is correct
76	Correct	119 ms	11680 KB	Output is correct
77	Correct	130 ms	11748 KB	Output is correct
78	Correct	117 ms	11716 KB	Output is correct
79	Correct	127 ms	11692 KB	Output is correct
80	Correct	129 ms	11692 KB	Output is correct
81	Correct	122 ms	11520 KB	Output is correct
82	Correct	126 ms	11808 KB	Output is correct
83	Correct	124 ms	11852 KB	Output is correct
84	Correct	121 ms	11528 KB	Output is correct
85	Correct	122 ms	11596 KB	Output is correct
86	Correct	129 ms	11880 KB	Output is correct
87	Correct	126 ms	11772 KB	Output is correct
88	Correct	122 ms	11664 KB	Output is correct
89	Correct	129 ms	11652 KB	Output is correct
90	Correct	131 ms	11728 KB	Output is correct
91	Correct	124 ms	11600 KB	Output is correct