結果
| 問題 | No.3622 Perfect Matching of Crab |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-08-15 00:38:22 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
AC
|
| 実行時間 | 634 ms / 2,000 ms |
| + 381µs | |
| コード長 | 22,885 bytes |
| 記録 | |
| コンパイル時間 | 2,177 ms |
| コンパイル使用メモリ | 110,152 KB |
| 実行使用メモリ | 103,876 KB |
| 最終ジャッジ日時 | 2026-08-15 00:38:33 |
| 合計ジャッジ時間 | 10,486 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 16 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.PrimitiveIterator.OfInt;
import java.util.PrimitiveIterator;
import java.util.Queue;
import java.util.Random;
import java.util.function.IntBinaryOperator;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.Predicate;
import java.util.function.ToIntFunction;
import java.util.random.RandomGenerator;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Main {
static MyPrintWriter pw = MyPrintWriter.getInstance();
static FastScanner sc = FastScanner.getInstance();
public static void main(String[] args) throws IOException {
Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
new Main().run();
pw.flush();
}
void run() {
int T = sc.nextInt();
for (int TEST = 0; TEST < T; TEST++) {
int N = sc.nextInt();
int[] X = new int[2 * N];
int[] Y = new int[2 * N];
boolean[] F = new boolean[2 * N];
for (int i = 0; i < (2 * N); i++) {
X[i] = sc.nextInt();
Y[i] = sc.nextInt();
F[i] = sc.next().charAt(0) == 'x';
}
IntTreapMultiSet set0 = new IntTreapMultiSet();
IntTreapMultiSet set1 = new IntTreapMultiSet();
for (int i = 0; i < (2 * N); i++) {
if (F[i]) {
set0.add(Y[i]);
} else {
set1.add(X[i]);
}
}
int c0 = 0;
int c1 = 0;
IntArrayList list0 = new IntArrayList();
IntArrayList list1 = new IntArrayList();
for (var es : set0.entryList()) {
list0.add(((int) (es.value)));
}
for (var es : set1.entryList()) {
list1.add(((int) (es.value)));
}
for (int i = 0; i < list0.size(); i++) {
if ((list0.get(i) % 2) == 1) {
list0.set(i, list0.get(i) - 1);
c0++;
}
}
for (int i = 0; i < list1.size(); i++) {
if ((list1.get(i) % 2) == 1) {
list1.set(i, list1.get(i) - 1);
c1++;
}
}
int m = Math.min(c0, c1);
c0 -= m;
c1 -= m;
if (c0 > 0) {
pw.printlnYesNo(ArrayUtils.sum(list1.toArray()) >= c0);
} else if (c1 > 0) {
pw.printlnYesNo(ArrayUtils.sum(list0.toArray()) >= c1);
} else {
pw.println("Yes");
}
}
}
}
class ArrayUtils {
public static long sum(int[] a) {
long ret = 0;
for (int val : a) {
ret += val;
}
return ret;
}
}
class FastScanner {
private static FastScanner instance = null;
private final InputStream in = System.in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int buflen = 0;
private FastScanner() {
}
public static FastScanner getInstance() {
if (instance == null) {
instance = new FastScanner();
}
return instance;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return buflen > 0;
}
private int readByte() {
if (hasNextByte()) {
return buffer[ptr++];
} else {
return -1;
}
}
private boolean isPrintableChar(int c) {
return (33 <= c) && (c <= 126);
}
public boolean hasNext() {
while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
ptr++;
}
return hasNextByte();
}
public String next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) {
throw new NoSuchElementException();
}
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
while ((b >= '0') && (b <= '9')) {
// n = n * 10 + (b - '0');
n = ((n << 1) + (n << 3)) + (b - '0');
b = readByte();
}
return minus ? -n : n;
}
public int nextInt() {
return ((int) (nextLong()));
}
}
/**
* *
* tailがa.lengthに比べて小さくなっても配列を取り直さない。
*
* @param <T>
*/
class IntArrayList implements Iterable<Integer> {
@SuppressWarnings("unchecked")
int defaultCapacity = 16;
int[] a;
public int tail = 0;
public IntArrayList() {
a = new int[defaultCapacity];
}
public void add(int v) {
if (tail == a.length) {
resize(2 * a.length);
}
a[tail] = v;
tail++;
}
public int get(int id) {
if ((id < 0) || (id >= tail)) {
throw new IndexOutOfBoundsException(((((("get(" + id) + ")は添え字") + 0) + "以上") + (tail - 1)) + "以下に違反");
}
return a[id];
}
public void set(int id, int value) {
if ((id < 0) || (id >= tail)) {
throw new IndexOutOfBoundsException();
}
a[id] = value;
}
void resize(int size) {
a = Arrays.copyOf(a, size);
}
public int size() {
return tail;
}
public int[] toArray() {
return Arrays.copyOf(a, tail);
}
@Override
public PrimitiveIterator.OfInt iterator() {
return new PrimitiveIterator.OfInt() {
int idx = 0;
@Override
public boolean hasNext() {
return idx < tail;
}
@Override
public int nextInt() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return get(idx++);
}
};
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (!(o instanceof IntArrayList that)) {
return false;
}
if (tail != that.tail) {
return false;
}
for (int i = 0; i < tail; i++) {
if (a[i] != that.a[i]) {
return false;
}
}
return true;
}
@Override
public int hashCode() {
int result = 1;
for (int i = 0; i < tail; i++) {
result = (31 * result) + a[i];
}
return result;
}
@Override
public String toString() {
return Arrays.toString(toArray());
}
}
/**
* {@code int} に特殊化した Treap ベースのマルチセット。
* 内部で {@link TreapMap} を使用しています。
*/
class IntTreapMultiSet {
private final TreapMap map;
/**
* 重複を含めた総要素数
*/
private long size = 0;
public IntTreapMultiSet() {
map = new TreapMap();
}
/**
* 要素を {@code repeat} 回追加します。
* {@code repeat} が負の場合は削除を意味しますが、操作後の個数が負になる場合は {@link AssertionError} を投げます。
*
* @param element
* 追加する要素
* @param repeat
* 追加する回数
* @complexity O(log N) (N は異なる要素の数)
*/
public void add(int element, long repeat) {
if (repeat == 0) {
return;
}
size += repeat;
long num = map.getOrDefault(element, 0L) + repeat;
if (num < 0) {
throw new AssertionError();
}
if (num == 0) {
map.remove(element);
} else {
map.put(element, num);
}
}
/**
* 要素を1つ追加します。
*
* @param element
* 追加する要素
* @complexity O(log N)
*/
public void add(int element) {
add(element, 1);
}
public static class Entry {
public final int key;
public final long value;
public Entry(int key, long value) {
this.key = key;
this.value = value;
}
}
/**
* キーが要素、値が要素の個数であるエントリーのリストを返します。
*
* @return エントリーのリスト
* @complexity O(N)
*/
public List<Entry> entryList() {
List<Entry> res = new ArrayList<>();
for (var e : map.entryList()) {
res.add(new Entry(((int) (e.key)), e.value));
}
return res;
}
/**
* 異なる要素の数を返します。
*
* @return 異なる要素の数
* @complexity O(1)
*/
public int numberDistinctElements() {
return map.size();
}
/**
* 集合が空であるかどうかを返します。
*
* @return 空であれば {@code true}
* @complexity O(1)
*/
public boolean isEmpty() {
return map.isEmpty();
}
/**
* 集合の状態を文字列として表します。
* <ul>
* <li>事前条件: 特になし。</li>
* <li>事後条件: 特になし。</li>
* <li>計算量: $O(N)$</li>
* <li>破壊的変更: なし。</li>
* </ul>
*
* @return 集合の状態を表す文字列
*/
// 未テスト
@Override
public String toString() {
if (isEmpty()) {
return "空集合";
} else {
StringBuilder sb = new StringBuilder();
boolean first = true;
for (var entry : entryList()) {
if (!first) {
sb.append("\n");
}
sb.append(entry.key).append(" が ").append(entry.value).append("個");
first = false;
}
return sb.toString();
}
}
/**
* このマルチセットと別のオブジェクトの同値性を判定します。
* 内部の各要素とその個数が一致する場合に同値とみなします。
*
* <p>計算量: $O(N)$（$N$ は異なる要素の数）</p>
*
* @param obj
* 比較対象のオブジェクト
* @return 同値であれば true, そうでなければ false
*/
// 未テスト
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof IntTreapMultiSet)) {
return false;
}
IntTreapMultiSet other = ((IntTreapMultiSet) (obj));
if (this.size != other.size) {
return false;
}
if (this.numberDistinctElements() != other.numberDistinctElements()) {
return false;
}
List<Entry> thisEntries = this.entryList();
List<Entry> otherEntries = other.entryList();
if (thisEntries.size() != otherEntries.size()) {
return false;
}
for (int i = 0; i < thisEntries.size(); i++) {
Entry e1 = thisEntries.get(i);
Entry e2 = otherEntries.get(i);
if ((e1.key != e2.key) || (e1.value != e2.value)) {
return false;
}
}
return true;
}
/**
* このマルチセットのハッシュコードを計算します。
*
* <p>計算量: $O(N)$（$N$ は異なる要素の数）</p>
*
* @return ハッシュコード
*/
// 未テスト
@Override
public int hashCode() {
int result = 1;
result = (31 * result) + Long.hashCode(size);
for (Entry e : entryList()) {
result = (31 * result) + Integer.hashCode(e.key);
result = (31 * result) + Long.hashCode(e.value);
}
return result;
}
}
class MyPrintWriter extends PrintWriter {
private static MyPrintWriter instance = null;
private MyPrintWriter() {
super(System.out);
}
public static MyPrintWriter getInstance() {
if (instance == null) {
instance = new MyPrintWriter();
}
return instance;
}
public void printlnYesNo(boolean flag) {
println(flag ? "Yes" : "No");
}
}
/**
* <ul>
* <li>キーに関して二分探索木の順序を満たす</li>
* <li>優先度(priority)に関して最大ヒープの性質を満たす</li>
* </ul>
*/
class TreapMap {
static final Random rnd = new Random();
private int size = 0;
public TreapMap() {
}
static class Node {
long key;
int priority;
Node left;
Node right;
int size;
long sum;
long val;
public Node(long key, long val) {
this.key = key;
this.val = val;
this.priority = rnd.nextInt();
recalc(this);
}
}
private Node root;
public static void recalc(Node t) {
if (t == null) {
return;
}
t.sum = t.val;
t.size = 1;
if (t.left != null) {
t.sum += t.left.sum;
t.size += t.left.size;
}
if (t.right != null) {
t.sum += t.right.sum;
t.size += t.right.size;
}
}
/**
* 右回転（Right Rotation）を行います。
*
* <p>次のように部分木を右回転させます：
*
* <pre>
* y x
* / \ => / \
* x C A y
* / \ / \
* A B B C
* </pre>
*
* @param y
* 回転対象となる部分木の根
* @return 回転後の新しい部分木の根
*/
private Node rotateRight(Node y) {
Node x = y.left;
y.left = x.right;
x.right = y;
recalc(y);
recalc(x);
return x;
}
/**
* 左回転（Left Rotation）を行います。
*
* <p>次のように部分木を左回転させます：
*
* <pre>
* x y
* / \ => / \
* A y x C
* / \ / \
* B C A B
* </pre>
*
* @param x
* 回転対象となる部分木の根
* @return 回転後の新しい部分木の根
*/
private Node rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
recalc(x);
recalc(y);
return y;
}
private Node put(Node node, long key, long val) {
if (node == null) {
++size;
return new Node(key, val);
}
if (key < node.key) {
node.left = put(node.left, key, val);
if (node.left.priority > node.priority) {
node = rotateRight(node);
}
} else if (key > node.key) {
node.right = put(node.right, key, val);
if (node.right.priority > node.priority) {
node = rotateLeft(node);
}
} else {
node.val = val;
}
recalc(node);
return node;
}
public void put(long key, long val) {
root = put(root, key, val);
}
public long getOrDefault(long key, long defaultValue) {
return getOrDefaultValue(getRoot(), key, defaultValue);
}
private long getOrDefaultValue(Node node, long key, long defaultValue) {
if (node == null) {
return defaultValue;
}
if (key == node.key) {
return node.val;
}
return key < node.key ? getOrDefaultValue(node.left, key, defaultValue) : getOrDefaultValue(node.right, key, defaultValue);
}
/**
* Treap から指定したキーを削除。
*
* <p>
* 削除は次の手順で行われます：
* <ol>
* <li>二分探索木として削除対象ノードを見つける</li>
* <li>優先度に応じて回転し、削除対象ノードを葉へ押し下げる</li>
* <li>葉になったら削除する</li>
* </ol>
*
* @param node
* 部分木の根
* @param key
* 削除するキー
* @return 更新後の部分木の根
https://judge.yosupo.jp/submission/336359
*/
private Node remove(Node node, long key) {
if (node == null) {
return null;
}
if (key < node.key) {
node.left = remove(node.left, key);
} else if (key > node.key) {
node.right = remove(node.right, key);
} else if ((node.left == null) && (node.right == null)) {
--size;
return null;
} else if (node.left == null) {
node = rotateLeft(node);
node.left = remove(node.left, key);
} else if (node.right == null) {
node = rotateRight(node);
node.right = remove(node.right, key);
} else if (node.left.priority > node.right.priority) {
node = rotateRight(node);
node.right = remove(node.right, key);
} else {
node = rotateLeft(node);
node.left = remove(node.left, key);
}
recalc(node);
return node;
}
public void remove(long key) {
root = remove(getRoot(), key);
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public static class Entry {
public final long key;
public final long value;
public Entry(long key, long value) {
this.key = key;
this.value = value;
}
}
/**
* https://atcoder.jp/contests/abc406/submissions/73198102
*
* @return */
public List<Entry> entryList() {
List<Entry> res = new ArrayList<>();
inOrderEntries(getRoot(), res);
return res;
}
private void inOrderEntries(Node node, List<Entry> res) {
if (node == null) {
return;
}
inOrderEntries(node.left, res);
res.add(new Entry(node.key, node.val));
inOrderEntries(node.right, res);
}
public Node getRoot() {
return root;
}
/**
* このマップと指定されたオブジェクトが等価であるか検証します。
*
* @param o
* 比較対象のオブジェクト
* @return 等価であれば true, そうでなければ false
$O(N)$
// 未テスト
*/
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (!(o instanceof TreapMap)) {
return false;
}
TreapMap other = ((TreapMap) (o));
if (this.size() != other.size()) {
return false;
}
List<Entry> thisEntries = this.entryList();
List<Entry> otherEntries = other.entryList();
for (int i = 0; i < thisEntries.size(); i++) {
Entry e1 = thisEntries.get(i);
Entry e2 = otherEntries.get(i);
if ((e1.key != e2.key) || (e1.value != e2.value)) {
return false;
}
}
return true;
}
/**
* このマップのハッシュコード値を返します。
*
* @return ハッシュコード値
$O(N)$
// 未テスト
*/
@Override
public int hashCode() {
int h = 0;
List<Entry> entries = this.entryList();
for (Entry entry : entries) {
h += Long.hashCode(entry.key) ^ Long.hashCode(entry.value);
}
return h;
}
}
// --- Original Code ---
//
//
// import java.io.IOException;
// import java.util.Arrays;
//
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.ArrayUtils;
// import library.util.collections.IntArrayList;
// import library.util.collections.IntTreapMultiSet;
//
// public class Main {
// static MyPrintWriter pw = MyPrintWriter.getInstance();
// static FastScanner sc = FastScanner.getInstance();
//
// public static void main(String[] args) throws IOException {
// new Main().run();
// pw.flush();
// MergeFiles.export();
// }
//
//
// void run() {
// int T=sc.nextInt();
// for (int TEST = 0; TEST < T; TEST++) {
// int N=sc.nextInt();
// int[]X=new int[2*N];
// int[]Y=new int[2*N];
// boolean[]F=new boolean[2*N];
// for (int i = 0; i < 2*N; i++) {
// X[i]=sc.nextInt();
// Y[i]=sc.nextInt();
// F[i]=sc.next().charAt(0)=='x';
// }
// IntTreapMultiSet set0=new IntTreapMultiSet();
// IntTreapMultiSet set1=new IntTreapMultiSet();
// for (int i = 0; i < 2*N; i++) {
// if(F[i]) {
// set0.add(Y[i]);
// } else {
// set1.add(X[i]);
// }
// }
// int c0=0;
// int c1=0;
// IntArrayList list0=new IntArrayList();
// IntArrayList list1=new IntArrayList();
// for (var es : set0.entryList()) {
// list0.add((int)es.value);
// }
// for (var es : set1.entryList()) {
// list1.add((int)es.value);
// }
// for (int i = 0; i < list0.size(); i++) {
// if(list0.get(i)%2==1) {
// list0.set(i, list0.get(i)-1);
// c0++;
// }
// }
// for (int i = 0; i < list1.size(); i++) {
// if(list1.get(i)%2==1) {
// list1.set(i, list1.get(i)-1);
// c1++;
// }
// }
// int m=Math.min(c0, c1);
// c0-=m;
// c1-=m;
// if (c0 > 0) {
// pw.printlnYesNo(ArrayUtils.sum(list1.toArray()) >= c0);
// } else if (c1 > 0) {
// pw.printlnYesNo(ArrayUtils.sum(list0.toArray()) >= c1);
// } else {
// pw.println("Yes");
// }
// }
// }
//
// void tr(Object... objects) {
// System.out.println(Arrays.deepToString(objects));
// }
// }
//