# Problem 7 / Both heuristics

Nov 19th, 2018
276
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import java.io.OutputStream;
2. import java.io.IOException;
3. import java.io.InputStream;
4. import java.io.OutputStream;
5. import java.io.PrintWriter;
6. import java.util.Arrays;
7. import java.io.BufferedWriter;
8. import java.util.InputMismatchException;
9. import java.io.IOException;
10. import java.util.ArrayList;
11. import java.util.List;
12. import java.io.Writer;
13. import java.io.OutputStreamWriter;
14. import java.io.InputStream;
15.
16. /**
17.  * Built using CHelper plug-in
18.  * Actual solution is at the top
19.  *
20.  * @author Rustam Musin (t.me/musin_acm)
21.  */
22. public class Main {
23.     public static void main(String[] args) {
24.         InputStream inputStream = System.in;
25.         OutputStream outputStream = System.out;
27.         OutputWriter out = new OutputWriter(outputStream);
29.         solver.solve(1, in, out);
30.         out.close();
31.     }
32.
34.         IntIntPair[] a;
35.         int n;
36.         int[][] g;
37.         Query[] queries;
38.
39.         public void solve(int testNumber, InputReader in, OutputWriter out) {
41.             new Solver().solve();
42.             for (Query q : queries) {
43.                 out.printLine(q.fail ? "fail" : "ok");
44.             }
45.         }
46.
47.         int find(IntIntPair[] a, IntIntPair p) {
48.             return Arrays.binarySearch(a, p);
49.         }
50.
53.             a = new IntIntPair[n];
54.             for (int i = 0; i < n; i++) {
56.             }
57.             Arrays.sort(a);
58.             int[] size = new int[n];
59.             int[] dx = {-1, 0, 1, 0};
60.             int[] dy = {0, 1, 0, -1};
61.             for (IntIntPair p : a) {
62.                 int cur = find(a, p);
63.                 for (int d = 0; d < 4; d++) {
64.                     int x = p.first + dx[d];
65.                     int y = p.second + dy[d];
66.                     int id = find(a, IntIntPair.makePair(x, y));
67.                     if (id >= 0) {
68.                         size[cur]++;
69.                     }
70.                 }
71.             }
72.             g = new int[n][];
73.             for (int i = 0; i < n; i++) {
74.                 g[i] = new int[size[i]];
75.             }
76.             for (IntIntPair p : a) {
77.                 int cur = find(a, p);
78.                 for (int d = 0; d < 4; d++) {
79.                     int x = p.first + dx[d];
80.                     int y = p.second + dy[d];
81.                     int id = find(a, IntIntPair.makePair(x, y));
82.                     if (id >= 0) {
83.                         g[cur][--size[cur]] = id;
84.                     }
85.                 }
86.             }
88.             queries = new Query[queryCount];
89.             for (int i = 0; i < queryCount; i++) {
93.                 int[] monsters = new int[monsterCount];
94.                 for (int j = 0; j < monsterCount; j++) {
96.                 }
97.                 int[] weapons = new int[weaponCount];
98.                 for (int j = 0; j < weaponCount; j++) {
100.                 }
101.                 queries[i] = new Query(i, player, weapons, monsters);
102.             }
103.         }
104.
105.         class Solver {
106.             List<Integer>[] tree;
107.             int treeN;
108.             boolean[] isActive;
109.             List<Integer> notRemoved;
110.             DSU dsu;
111.
112.             void solve() {
113.                 buildTree();
114.                 dsu = new DSU();
115.                 isActive = new boolean[n];
116.                 notRemoved = new ArrayList<>();
117.                 for (int i = 0; i < n; i++) {
119.                 }
120.                 dfs(1);
121.             }
122.
123.             void buildTree() {
124.                 int log = 1;
125.                 while (1 << log < queries.length) {
126.                     log++;
127.                 }
128.                 treeN = 1 << log;
129.                 tree = new List[2 * treeN];
130.                 for (int i = 0; i < tree.length; i++) {
131.                     tree[i] = new ArrayList<>();
132.                 }
133.                 for (int i = 0; i < queries.length; i++) {
134.                     for (int w : queries[i].weapons) {
136.                     }
137.                 }
138.                 for (int i = treeN - 1; i > 0; i--) {
139.                     List<Integer> both = new ArrayList<>();
140.                     int leftAt = 0;
141.                     int rightAt = 0;
142.                     List<Integer> leftCh = tree[i * 2];
143.                     List<Integer> rightCh = tree[i * 2 + 1];
144.                     while (leftAt < leftCh.size() && rightAt < rightCh.size()) {
145.                         if (leftCh.get(leftAt) == (int) rightCh.get(rightAt)) {
147.                             leftAt++;
148.                             rightAt++;
149.                         } else if (leftCh.get(leftAt) < rightCh.get(rightAt)) {
151.                         } else {
153.                         }
154.                     }
155.                     while (leftAt < leftCh.size()) {
157.                     }
158.                     while (rightAt < rightCh.size()) {
160.                     }
161.                     tree[i] = both;
162.                 }
163.             }
164.
165.             void dfs(int v) {
166.                 int startActions = dsu.actions.size();
167.                 List<Integer> newNotRemoved = new ArrayList<>();
168.                 List<Integer> removed = new ArrayList<>();
169.                 int at = 0;
170.                 for (int x : notRemoved) {
171.                     while (at < tree[v].size() && tree[v].get(at) < x) {
172.                         at++;
173.                     }
174.                     if (at < tree[v].size() && tree[v].get(at) == x) {
176.                     } else {
177.                         isActive[x] = true;
178.                         for (int to : g[x]) {
179.                             if (isActive[to]) {
180.                                 dsu.unite(x, to);
181.                             }
182.                         }
184.                     }
185.                 }
186.                 if (v < treeN) {
187.                     List<Integer> old = notRemoved;
188.                     notRemoved = newNotRemoved;
189.                     dfs(v * 2);
190.                     dfs(v * 2 + 1);
191.                     notRemoved = old;
192.                 } else {
193.                     if (v - treeN < queries.length) {
194.                         Query query = queries[v - treeN];
195.                         for (int monster : query.monsters) {
196.                             query.fail |= dsu.find(query.player) == dsu.find(monster);
197.                         }
198.                     }
199.                 }
200.                 for (int x : removed) {
201.                     isActive[x] = false;
202.                 }
203.                 dsu.restore(startActions);
204.             }
205.
206.         }
207.
208.         class Query {
209.             int index;
210.             int player;
211.             int[] weapons;
212.             int[] monsters;
213.             boolean fail;
214.
215.             Query(int index, int player, int[] weapons, int[] monsters) {
216.                 this.index = index;
217.                 this.player = player;
218.                 this.weapons = weapons;
219.                 this.monsters = monsters;
220.                 Arrays.sort(weapons);
221.                 Arrays.sort(monsters);
222.             }
223.
224.         }
225.
226.         enum ActionType {
227.             PARENT,
228.             RANK,
229.             ;
230.         }
231.
232.         class Action {
234.             int index;
235.             int value;
236.
237.             Action(Task7.ActionType type, int index, int value) {
238.                 this.type = type;
239.                 this.index = index;
240.                 this.value = value;
241.             }
242.
243.         }
244.
245.         class DSU {
246.             int[] parent;
247.             int[] rank;
248.             List<Action> actions = new ArrayList<>();
249.
250.             DSU() {
251.                 parent = new int[n];
252.                 rank = new int[n];
253.                 for (int i = 0; i < n; i++) {
254.                     parent[i] = i;
255.                     rank[i] = 1;
256.                 }
257.             }
258.
259.             void saveChange(boolean parent, int index, int value) {
260.                 if (parent) {
262.                 } else {
264.                 }
265.             }
266.
267.             int find(int v) {
268.                 if (parent[v] == v) {
269.                     return v;
270.                 }
271.                 saveChange(true, v, parent[v]);
272.                 return parent[v] = find(parent[v]);
273.             }
274.
275.             boolean unite(int u, int v) {
276.                 u = find(u);
277.                 v = find(v);
278.                 if (u == v) {
279.                     return false;
280.                 }
281.                 if (rank[u] > rank[v]) {
282.                     return unite(v, u);
283.                 }
284.                 saveChange(true, u, parent[u]);
285.                 saveChange(false, v, rank[v]);
286.                 parent[u] = v;
287.                 rank[v] = Math.max(rank[v], rank[u] + 1);
288.                 return true;
289.             }
290.
291.             void restore(int leftActions) {
292.                 while (actions.size() > leftActions) {
293.                     Action action = actions.get(actions.size() - 1);
294.                     actions.remove(actions.size() - 1);
295.                     if (action.type == Task7.ActionType.PARENT) {
296.                         parent[action.index] = action.value;
297.                     } else {
298.                         rank[action.index] = action.value;
299.                     }
300.                 }
301.             }
302.
303.         }
304.
305.     }
306.
307.     static class IntIntPair implements Comparable<IntIntPair> {
308.         public final int first;
309.         public final int second;
310.
311.         public static IntIntPair makePair(int first, int second) {
312.             return new IntIntPair(first, second);
313.         }
314.
315.         public IntIntPair(int first, int second) {
316.             this.first = first;
317.             this.second = second;
318.         }
319.
320.         public boolean equals(Object o) {
321.             if (this == o) {
322.                 return true;
323.             }
324.             if (o == null || getClass() != o.getClass()) {
325.                 return false;
326.             }
327.
328.             IntIntPair pair = (IntIntPair) o;
329.
330.             return first == pair.first && second == pair.second;
331.         }
332.
333.         public int hashCode() {
334.             int result = first;
335.             result = 31 * result + second;
336.             return result;
337.         }
338.
339.         public String toString() {
340.             return "(" + first + "," + second + ")";
341.         }
342.
343.         public int compareTo(IntIntPair o) {
344.             int value = Integer.compare(first, o.first);
345.             if (value != 0) {
346.                 return value;
347.             }
348.             return Integer.compare(second, o.second);
349.         }
350.
351.     }
352.
353.     static class OutputWriter {
354.         private final PrintWriter writer;
355.
356.         public OutputWriter(OutputStream outputStream) {
357.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
358.         }
359.
360.         public OutputWriter(Writer writer) {
361.             this.writer = new PrintWriter(writer);
362.         }
363.
364.         public void print(Object... objects) {
365.             for (int i = 0; i < objects.length; i++) {
366.                 if (i != 0) {
367.                     writer.print(' ');
368.                 }
369.                 writer.print(objects[i]);
370.             }
371.         }
372.
373.         public void printLine(Object... objects) {
374.             print(objects);
375.             writer.println();
376.         }
377.
378.         public void close() {
379.             writer.close();
380.         }
381.
382.     }
383.
385.         private InputStream stream;
386.         private byte[] buf = new byte[1024];
387.         private int curChar;
388.         private int numChars;
390.
392.             this.stream = stream;
393.         }
394.
396.             if (numChars == -1) {
397.                 throw new InputMismatchException();
398.             }
399.             if (curChar >= numChars) {
400.                 curChar = 0;
401.                 try {
403.                 } catch (IOException e) {
404.                     throw new InputMismatchException();
405.                 }
406.                 if (numChars <= 0) {
407.                     return -1;
408.                 }
409.             }
410.             return buf[curChar++];
411.         }
412.
415.             while (isSpaceChar(c)) {
417.             }
418.             int sgn = 1;
419.             if (c == '-') {
420.                 sgn = -1;
422.             }
423.             int res = 0;
424.             do {
425.                 if (c < '0' || c > '9') {
426.                     throw new InputMismatchException();
427.                 }
428.                 res *= 10;
429.                 res += c - '0';
431.             } while (!isSpaceChar(c));
432.             return res * sgn;
433.         }
434.
435.         public boolean isSpaceChar(int c) {
436.             if (filter != null) {
437.                 return filter.isSpaceChar(c);
438.             }
439.             return isWhitespace(c);
440.         }
441.
442.         public static boolean isWhitespace(int c) {
443.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
444.         }
445.
446.         public interface SpaceCharFilter {
447.             public boolean isSpaceChar(int ch);
448.
449.         }
450.
451.     }
452. }