結果
| 問題 | No.624 Santa Claus and The Last Dungeon |
| ユーザー |
 37zigen
|
| 提出日時 | 2018-01-07 01:58:07 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,789 ms / 2,000 ms |
| コード長 | 8,998 bytes |
| コンパイル時間 | 2,999 ms |
| コンパイル使用メモリ | 83,084 KB |
| 実行使用メモリ | 82,628 KB |
| 平均クエリ数 | 407.97 |
| 最終ジャッジ日時 | 2024-07-16 15:20:51 |
| 合計ジャッジ時間 | 65,000 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 36 |
ソースコード
import java.io.FileNotFoundException;import java.util.Arrays;import java.util.Scanner;class Main {int N = 100;Scanner sc = new Scanner(System.in);int[] num = new int[N];AVLTree pnd = new AVLTree();{for (int i = 0; i < N; ++i) {pnd.insert(i);}}public void run() {int Q = sc.nextInt();Arrays.fill(num, -1);for (int i = 0; i < N; i += 2) {dfs1(1, pnd.sz + 1, i, i + 1);}for (int i = 0; i < N; ++i) {System.out.print(num[i] / 10 + "" + num[i] % 10);if (num[i] == -1)throw new AssertionError();System.out.print(i == N - 1 ? "\n" : " ");}}void dfs1(int l, int r, int u, int v) {int lp = (int) pnd.kth(l).key;int mp = (int) pnd.kth((l + r) / 2).key;int rp = (int) pnd.kth(r - 1).key;if (r - l == 1) {throw new AssertionError();}for (int i = 0; i < N; ++i) {if (num[i] != -1) {System.out.print("??");} else {if (lp <= i && i < mp) {System.out.print(u / 10 + "" + u % 10);} else if (mp <= i && i <= rp) {System.out.print(v / 10 + "" + v % 10);} else {System.out.print("??");}}System.out.print(i == N - 1 ? "\n" : " ");}int p0 = sc.nextInt();int p1 = sc.nextInt();int p2 = sc.nextInt();if (p2 == 2) {dfs2(l, (l + r) / 2, (l + r) / 2, r, u, v);} else if (p2 == 1) {int mp2 = (int) pnd.kth((l + (l + r) / 2) / 2).key;for (int i = 0; i < N; ++i) {if (num[i] != -1) {System.out.print("??");} else {if (mp <= i && i <= rp) {System.out.print(v / 10 + "" + v % 10);} else {System.out.print("??");}}System.out.print(i == N - 1 ? "\n" : " ");}p0 = sc.nextInt();p1 = sc.nextInt();p2 = sc.nextInt();if (p2 == 1) {dfs1((l + r) / 2, r, u, v);} else if (p2 == 0) {dfs1(l, (l + r) / 2, u, v);} else {throw new AssertionError();}} else {dfs2(l, (l + r) / 2, (l + r) / 2, r, v, u);}}void dfs2(int l1, int r1, int l2, int r2, int u, int v) {int lp1 = (int) pnd.kth(l1).key;int mp1 = (int) pnd.kth((l1 + r1) / 2).key;int rp1 = (int) pnd.kth(r1 - 1).key;int lp2 = (int) pnd.kth(l2).key;int mp2 = (int) pnd.kth((l2 + r2) / 2).key;int rp2 = (int) pnd.kth(r2 - 1).key;if (r1 - l1 == 1 && r2 - l2 == 1) {num[lp1] = u;num[lp2] = v;pnd.delete(lp1);pnd.delete(lp2);return;}for (int i = 0; i < N; ++i) {if (num[i] != -1) {System.out.print("??");} else {if (lp1 <= i && i < mp1) {System.out.print(u / 10 + "" + u % 10);} else if (lp2 <= i && i < mp2) {System.out.print(v / 10 + "" + v % 10);} else {System.out.print("??");}}System.out.print(i == N - 1 ? "\n" : " ");}int p0 = sc.nextInt();int p1 = sc.nextInt();int p2 = sc.nextInt();if (p2 == 2) {dfs2(l1, (l1 + r1) / 2, l2, (l2 + r2) / 2, u, v);} else if (p2 == 1) {for (int i = 0; i < N; ++i) {if (num[i] != -1) {System.out.print("??");} else {if (mp1 <= i && i <= rp1) {System.out.print(u / 10 + "" + u % 10);} else if (lp2 <= i && i < mp2) {System.out.print(v / 10 + "" + v % 10);} else {System.out.print("??");}}System.out.print(i == N - 1 ? "\n" : " ");}p0 = sc.nextInt();p1 = sc.nextInt();p2 = sc.nextInt();if (p2 == 2) {dfs2((l1 + r1) / 2, r1, l2, (l2 + r2) / 2, u, v);} else if (p2 == 0) {dfs2(l1, (l1 + r1) / 2, (l2 + r2) / 2, r2, u, v);} else {throw new AssertionError();}} else {dfs2((l1 + r1) / 2, r1, (l2 + r2) / 2, r2, u, v);}}public static class AVLTree {Node root = null;int sz = 0;Node ceiling(long v) {Node node = root;while (node != null) {if (min(node.right) <= v) {node = node.right;} else if (node.key <= v)return node;elsenode = node.left;}return node;}Node floor(long v) {Node node = root;while (node != null) {if (max(node.left) >= v) {node = node.left;} else if (node.key >= v)return node;elsenode = node.right;}return node;}class Node {long key;long max;long min;int height;int balance;int sz = 1;Node left = null;Node right = null;Node parent = null;public Node(long key_, Node parent_) {key = key_;parent = parent_;max = key_;min = key_;}}Node kth(long a) {Node node = root;int sum = 0;while (node != null) {if (sum + node.sz < a) {return null;}if (sum + sz(node.left) + 1 == a) {return node;}if (sum + sz(node.left) + 1 < a) {sum = sum + 1 + sz(node.left);node = node.right;} else {node = node.left;}}return null;}boolean contain(int delKey) {if (root == null)return false;Node node = root;while (node != null) {if (delKey == node.key) {return true;}node = delKey >= node.key ? node.right : node.left;}return false;}boolean delete(long key) {if (root == null)return false;Node node = root;while (node != null) {if (key == node.key) {delete(node);--sz;return true;}node = key >= node.key ? node.right : node.left;}return false;}//boolean delete(long key) から呼び出す。private void delete(Node node) {if (node.left == null && node.right == null) {if (node.parent == null) {root = null;return;}Node parent = node.parent;if (parent.left == node)parent.left = null;elseparent.right = null;rebalance(parent);}if (node.left != null) {Node child = node.left;while (child.right != null) {child = child.right;}node.key = child.key;delete(child);} else if (node.right != null) {Node child = node.right;while (child.left != null) {child = child.left;}node.key = child.key;delete(child);}}boolean insert(long key) {if (root == null) {root = new Node(key, null);++sz;return true;}Node cur = root;Node parent = null;while (true) {if (cur.key == key) {return false;}parent = cur;boolean goLeft = key < cur.key;cur = goLeft ? cur.left : cur.right;if (cur == null) {if (goLeft) {parent.left = new Node(key, parent);} else {parent.right = new Node(key, parent);}rebalance(parent);break;}}++sz;return true;}void rebalance(Node n) {setBalance(n);if (n.balance == -2) {if (height(n.left.left) >= height(n.left.right)) {n = rotateRight(n);} else {n = rotateLeftThenRight(n);}} else if (n.balance == 2) {if (height(n.right.right) >= height(n.right.left)) {n = rotateLeft(n);} else {n = rotateRightThenLeft(n);}}if (n.parent != null) {rebalance(n.parent);} else {root = n;}}void setBalance(Node... nodes) {for (Node n : nodes) {n.height = 1 + Math.max(height(n.right), height(n.left));n.balance = height(n.right) - height(n.left);n.sz = 1 + sz(n.left) + sz(n.right);n.max = Math.max(n != null ? n.key : -Integer.MAX_VALUE, Math.max(max(n.left), max(n.right)));n.min = Math.min(n != null ? n.key : Integer.MAX_VALUE, Math.min(min(n.left), min(n.right)));}}int sz(Node node) {return node != null ? node.sz : 0;}int height(Node node) {return node != null ? node.height : -1;}long max(Node node) {return node != null ? node.max : -Long.MAX_VALUE;}long min(Node node) {return node != null ? node.min : Long.MAX_VALUE;}Node rotateRight(Node a) {Node b = a.left;if (a.parent != null) {if (a.parent.left == a) {a.parent.left = b;} else {a.parent.right = b;}}b.parent = a.parent;a.parent = b;a.left = b.right;b.right = a;if (a.left != null)a.left.parent = a;setBalance(a, b);return b;}Node rotateLeft(Node a) {Node b = a.right;if (a.parent != null) {if (a.parent.right == a) {a.parent.right = b;} else {a.parent.left = b;}}b.parent = a.parent;a.parent = b;a.right = b.left;b.left = a;if (a.right != null)a.right.parent = a;setBalance(a, b);return b;}Node rotateLeftThenRight(Node n) {n.left = rotateLeft(n.left);return rotateRight(n);}Node rotateRightThenLeft(Node n) {n.right = rotateRight(n.right);return rotateLeft(n);}void inOrder(Node cur) {if (cur == null)return;inOrder(cur.left);System.out.println(cur.key);inOrder(cur.right);}}void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}public static void main(String[] args) throws FileNotFoundException {new Main().run();}}