"Domination". Look it up.
-Scout, TF2
so, this problem.
it gives us a bunch of players who have 2 strengths- one for each of two maps
we can match two players on any of the two maps, and the player who's stronger
on that map wins without fail
it then asks us to calculate for each of the players if they can dominate all
the others, whether that be directly or indirectly
so first let's just sort all the players by map 1 strength
this way, if p2 comes after p1, we know that p2 can dominate p2 hard-on
NOTICE! that the rearranged answer array will always look like this:
why? i think we just have to prove two sub-things to get to the actual claim:
so let's get proofing ig
if hypothetically, for the sake of the argument, we had a can-dominate array like this:
``` 000111100001111000 ```
that would be insane, because the middle & leftmost segment of 0's can be
dominated through the right sequence of 1's
so yeah
ok say p2 came right after p1
now the domination array can only stay the same or increase, because p2 can dominate
everyone p1 has through p1, and maybe even dominate a bit more!
q.e.d. ez clap
now that the proof is done, we can just use binary search to find the breakpoint
to check if a player can dominate everyone we keep track of the maximum second map strength
that we can utilize and then while that strength can keep on expanding throughout the
rest of the playerbase we keep on updating that strength
if we get to the final player we win, and if we don't we lose!
code here:
```java import java.io.*; import java.util.*; public class GameMaster { public static void main(String[] args) throws IOException { BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); int testNum = Integer.parseInt(read.readLine()); for (int t = 0; t < testNum; t++) { int playerNum = Integer.parseInt(read.readLine()); StringTokenizer map1 = new StringTokenizer(read.readLine()); StringTokenizer map2 = new StringTokenizer(read.readLine()); int[][] players = new int[playerNum][]; for (int p = 0; p < playerNum; p++) { players[p] = new int[]{ Integer.parseInt(map1.nextToken()), Integer.parseInt(map2.nextToken()), p // keep track of the original index }; } // elements are guaranteed to be unique Arrays.sort(players, Comparator.comparingInt(p -> p[0])); /* * this[x] = if our current map strength is x, * what's the maximum index we can dominate up to (inclusive)? */ TreeMap<Integer, Integer> maxKills = new TreeMap<>(); for (int p = 0; p < players.length; p++) { maxKills.put(players[p][1], p); } int prev = Integer.MIN_VALUE; for (int i : maxKills.keySet()) { if (prev != Integer.MIN_VALUE) { maxKills.put(i, Math.max(maxKills.get(i), maxKills.get(prev))); } prev = i; } // this[p] = best map 2 strength up to player p int[] bestMap2 = new int[playerNum]; bestMap2[0] = players[0][1]; for (int p = 1; p < playerNum; p++) { bestMap2[p] = Math.max(bestMap2[p - 1], players[p][1]); } int lo = 0; int hi = playerNum - 1; int valid = -1; while (lo <= hi) { int mid = (lo + hi) / 2; int at = mid; while (maxKills.get(bestMap2[at]) != at) { at = maxKills.get(bestMap2[at]); } if (at == playerNum - 1) { valid = mid; hi = mid - 1; } else { lo = mid + 1; } } int[] possible = new int[playerNum]; for (int p = valid; p < playerNum; p++) { possible[players[p][2]] = 1; } for (int p = 0; p < playerNum; p++) { System.out.print(possible[p]); } System.out.println(); } } } ```