結果
| 問題 | No.2257 Swim and Sleep |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2023-03-24 23:08:18 |
| 言語 | D (dmd 2.106.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,710 bytes |
| コンパイル時間 | 1,440 ms |
| コンパイル使用メモリ | 156,612 KB |
| 実行使用メモリ | 23,116 KB |
| 最終ジャッジ日時 | 2024-06-22 17:40:35 |
| 合計ジャッジ時間 | 4,073 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,812 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | AC | 106 ms
6,940 KB |
| testcase_08 | AC | 118 ms
6,940 KB |
| testcase_09 | AC | 108 ms
6,944 KB |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/numeric.d(2999): Warning: cannot inline function `std.numeric.gcdImpl!ulong.gcdImpl`
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }
bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }
int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }
struct ModInt(uint M_) {
import std.conv : to;
alias M = M_;
uint x;
this(ModInt a) { x = a.x; }
this(uint x_) { x = x_ % M; }
this(ulong x_) { x = cast(uint)(x_ % M); }
this(int x_) { x = ((x_ %= cast(int)(M)) < 0) ? (x_ + cast(int)(M)) : x_; }
this(long x_) { x = cast(uint)(((x_ %= cast(long)(M)) < 0) ? (x_ + cast(long)(M)) : x_); }
ref ModInt opAssign(T)(inout(T) a) if (is(T == uint) || is(T == ulong) || is(T == int) || is(T == long)) { return this = ModInt(a); }
ref ModInt opOpAssign(string op, T)(T a) {
static if (is(T == ModInt)) {
static if (op == "+") { x = ((x += a.x) >= M) ? (x - M) : x; }
else static if (op == "-") { x = ((x -= a.x) >= M) ? (x + M) : x; }
else static if (op == "*") { x = cast(uint)((cast(ulong)(x) * a.x) % M); }
else static if (op == "/") { this *= a.inv(); }
else static assert(false);
return this;
} else static if (op == "^^") {
if (a < 0) return this = inv()^^(-a);
ModInt b = this, c = 1U;
for (long e = a; e; e >>= 1) { if (e & 1) c *= b; b *= b; }
return this = c;
} else {
return mixin("this " ~ op ~ "= ModInt(a)");
}
}
ModInt inv() const {
uint a = M, b = x; int y = 0, z = 1;
for (; b; ) { const q = a / b; const c = a - q * b; a = b; b = c; const w = y - cast(int)(q) * z; y = z; z = w; }
assert(a == 1); return ModInt(y);
}
ModInt opUnary(string op)() const {
static if (op == "+") { return this; }
else static if (op == "-") { ModInt a; a.x = x ? (M - x) : 0U; return a; }
else static assert(false);
}
ModInt opBinary(string op, T)(T a) const { return mixin("ModInt(this) " ~ op ~ "= a"); }
ModInt opBinaryRight(string op, T)(T a) const { return mixin("ModInt(a) " ~ op ~ "= this"); }
bool opCast(T: bool)() const { return (x != 0U); }
string toString() const { return x.to!string; }
}
enum MO = 998244353;
alias Mint = ModInt!MO;
void main() {
/*
debug {
foreach (m; 1 .. 8 + 1) foreach (n; 1 .. 8 + 1) if (m <= n) {
writefln("m = %s, n = %s", m, n);
writeln;
const g = gcd(m, n);
int cnt;
auto a = new int[][](m, n);
auto fs = new int[4][m];
auto gs = new int[4][n];
auto ps = new int[4][g];
auto qs = new int[4][g];
bool trivial() {
{
bool ok = true;
foreach (x; 0 .. m) ok = ok && (fs[x][1] == n || fs[x][3] == n);
if (ok) return true;
}
{
bool ok = true;
foreach (y; 0 .. n) ok = ok && (gs[y][0] == m || gs[y][2] == m);
if (ok) return true;
}
return false;
}
void dfs(int x, int y) {
if (x == m) {
++cnt;
if (!trivial) {
foreach (xx; 0 .. m) {
foreach (yy; 0 .. n) {
write("v>^<"[a[xx][yy]]);
}
writeln;
}
writeln;
}
} else if (y == n) {
dfs(x + 1, 0);
} else {
foreach (b; 0 .. 4) {
a[x][y] = b;
const z = (x + y) % g;
const w = (x + (n - y)) % g;
++fs[x][b];
++gs[y][b];
++ps[z][b];
++qs[w][b];
bool ok = true;
ok = ok && !(fs[x][1] && fs[x][3]);
ok = ok && !(gs[y][0] && gs[y][2]);
ok = ok && !(ps[z][0] && ps[z][1]);
ok = ok && !(ps[z][2] && ps[z][3]);
ok = ok && !(qs[w][0] && qs[w][3]);
ok = ok && !(qs[w][2] && qs[w][1]);
if (ok) {
dfs(x, y + 1);
}
--fs[x][b];
--gs[y][b];
--ps[z][b];
--qs[w][b];
}
}
}
dfs(0, 0);
stderr.writeln(m, " ", n, ": ", cnt);
stderr.flush;
writeln('-'.repeat(80).array);
writeln;
stdout.flush;
}
return;
}
//*/
try {
for (; ; ) {
const numCases = readInt;
foreach (caseId; 0 .. numCases) {
const M = readLong;
const N = readLong;
const K = readInt;
auto X = new long[K];
auto Y = new long[K];
auto D = new long[K];
foreach (k; 0 .. K) {
X[k] = readInt;
Y[k] = readInt;
D[k] = "RULD".indexOf(readToken[0]);
}
const G = gcd(M, N);
debug {
writefln("M = %s, N = %s, G = %s", M, N, G);
writeln("X = ", X);
writeln("Y = ", Y);
writeln("D = ", D);
}
int[long] fs, gs, ps, qs;
foreach (k; 0 .. K) {
const x = X[k];
const y = Y[k];
const z = (x + y) % G;
const w = (x + N - y) % G;
if (x !in fs) fs[x] = 0;
if (y !in gs) gs[y] = 0;
if (z !in ps) ps[z] = 0;
if (w !in qs) qs[w] = 0;
fs[x] |= 1 << D[k];
gs[y] |= 1 << D[k];
ps[z] |= 1 << D[k];
qs[w] |= 1 << D[k];
}
debug {
writeln("fs = ", fs);
writeln("gs = ", gs);
writeln("ps = ", ps);
writeln("qs = ", qs);
}
int all;
foreach (k; 0 .. K) {
all |= 1 << D[k];
}
Mint ans;
// trivial each x
{
bool ok = true;
long m = M;
foreach (x, f; fs) {
ok = ok && (f == 1 << 1 || f == 1 << 3);
--m;
}
if (ok) {
debug {
writefln("trivial each x: m = %s", m);
}
ans += Mint(2)^^m;
}
}
// trivial each y
{
bool ok = true;
long n = N;
foreach (y, g; gs) {
ok = ok && (g == 1 << 0 || g == 1 << 2);
--n;
}
if (ok) {
debug {
writefln("trivial each y: n = %s", n);
}
ans += Mint(2)^^n;
}
}
// 2 special
bool[2] oks;
if (G % 2 == 0) {
foreach (s; 0 .. 2) {
bool ok = true;
foreach (k; 0 .. K) {
ok = ok && (((X[k] + Y[k] + s) & 1) == (D[k] & 1));
}
long m = M, n = N;
foreach (x, f; fs) {
ok = ok && !((f >> 1 & 1) && (f >> 3 & 1));
if ((f >> 1 & 1) || (f >> 3 & 1)) --m;
}
foreach (y, g; gs) {
ok = ok && !((g >> 0 & 1) && (g >> 2 & 1));
if ((g >> 0 & 1) || (g >> 2 & 1)) --n;
}
if (ok) {
debug {
writefln("2 special: s = %s, m = %s, n = %s", s, m, n);
}
ans += Mint(2)^^(m + n);
}
oks[s] = ok;
}
}
debug {
writeln("oks = ", oks);
}
// other z
foreach (i; 0 .. 2) {
int d0, d1;
final switch (i) {
case 0: d0 = 0; d1 = 3; break;
case 1: d0 = 1; d1 = 2; break;
}
bool ok = true;
long g = G;
foreach (z, p; ps) {
ok = ok && (p == 1 << d0 || p == 1 << d1);
--g;
}
if (ok) {
Mint way = Mint(2)^^g;
if (all == 0 || all == 1 << d0) way -= 1;
if (all == 0 || all == 1 << d1) way -= 1;
foreach (s; 0 .. 2) if (oks[s]) way -= 1;
debug {
writefln("other z: d0 = %s, d1 = %s, way = %s", d0, d1, way);
}
ans += way;
}
}
// other w
foreach (i; 0 .. 2) {
int d0, d1;
final switch (i) {
case 0: d0 = 0; d1 = 1; break;
case 1: d0 = 2; d1 = 3; break;
}
bool ok = true;
long g = G;
foreach (w, q; qs) {
ok = ok && (q == 1 << d0 || q == 1 << d1);
--g;
}
if (ok) {
Mint way = Mint(2)^^g;
if (all == 0 || all == 1 << d0) way -= 1;
if (all == 0 || all == 1 << d1) way -= 1;
foreach (s; 0 .. 2) if (oks[s]) way -= 1;
debug {
writefln("other w: d0 = %s, d1 = %s, way = %s", d0, d1, way);
}
ans += way;
}
}
// TODO: 4 | G ga mada aru...
writeln(ans);
}
}
} catch (EOFException e) {
}
}