結果
| 問題 |
No.3335 ReCT
|
| コンテスト | |
| ユーザー |
 KumaTachiRen
|
| 提出日時 | 2025-11-07 23:14:10 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 12,716 bytes |
| コンパイル時間 | 8,194 ms |
| コンパイル使用メモリ | 171,108 KB |
| 実行使用メモリ | 46,152 KB |
| 最終ジャッジ日時 | 2025-11-07 23:14:24 |
| 合計ジャッジ時間 | 12,327 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 TLE * 1 |
| other | -- * 97 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (99 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using Lib;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.Contracts;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using static Lib.OutputLib;
public class Solver
{
const bool MultiTestCase = false;
void Solve()
{
int h = ri, w = ri;
CalcC(h, w);
CalcT(h, w);
CalcCT(h, w);
}
void CalcC(int h, int w)
{
int n = Math.Max(h, w);
var f = new bool[n + 1, n + 1];
for (int i = 0; i <= n; i++) f[i, 0] = true;
for (int j = 0; j <= n; j++) f[0, j] = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (i >= 4 && i % 2 == 0 && j >= 3) f[i, j] |= true;
if (i >= 3 && j >= 4 && j % 2 == 0) f[i, j] |= true;
if (i > 1 && j > 2) f[i, j] |= f[i - 1, j - 2];
if (i > 2 && j > 1) f[i, j] |= f[i - 2, j - 1];
}
var a = new int[h, w];
int cnt = 0;
void calc(int h, int w, Action<int, int, int> set)
{
if (h == 0 || w == 0) return;
if (!f[h, w])
{
cnt = -IINF;
return;
}
if (h >= 4 && h % 2 == 0 && w >= 3)
{
while (h >= 6)
{
for (int j = 0; j < w; j++)
{
set(0, j, cnt + 1);
set(1, j, cnt + 2);
set(2, j, cnt + 1);
set(3, j, cnt + 3);
set(4, j, cnt + 2);
set(5, j, cnt + 3);
}
set(1, 0, cnt + 1);
set(2, w - 1, cnt + 2);
set(3, w - 1, cnt + 2);
set(4, 0, cnt + 3);
cnt += 3;
h -= 6;
}
if (h >= 4)
{
for (int j = 0; j < w; j++)
{
set(0, j, cnt + 1);
set(1, j, cnt + 2);
set(2, j, cnt + 1);
set(3, j, cnt + 2);
}
set(1, 0, cnt + 1);
set(2, w - 1, cnt + 2);
cnt += 2;
h -= 4;
}
}
else if (h > 1 && w > 2 && f[h - 1, w - 2])
{
for (int i = 0; i < h; i++) set(i, 0, cnt + 1);
for (int i = 0; i < h; i++) set(i, w - 1, cnt + 1);
for (int j = 0; j < w; j++) set(0, j, cnt + 1);
cnt += 1;
calc(h - 1, w - 2, (i, j, v) => set(i + 1, j + 1, v));
}
else
{
calc(w, h, (i, j, v) => set(j, i, v));
}
}
calc(h, w, (i, j, v) => a[i, j] = v);
if (cnt < 0)
{
Contract.Assert(cnt >= 0);
Write(-1);
}
else
{
Write(cnt);
WriteMat(a);
}
}
void CalcT(int h, int w)
{
int n = Math.Max(h, w);
var f = new bool[n + 1, n + 1];
for (int i = 0; i <= n; i++) f[i, 0] = true;
for (int j = 0; j <= n; j++) f[0, j] = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (i >= 4 && j >= 4)
{
f[i, j] |= f[i - 4, j];
f[i, j] |= f[i, j - 4];
}
if (i > 2 && j > 3) f[i, j] |= f[i - 2, j - 3];
if (i > 3 && j > 2) f[i, j] |= f[i - 3, j - 2];
}
var a = new int[h, w];
int cnt = 0;
void calc(int h, int w, Action<int, int, int> set)
{
if (h == 0 || w == 0) return;
if (!f[h, w])
{
cnt = -IINF;
return;
}
if (h > 3 && w > 2 && f[h - 3, w - 2])
{
for (int i = 0; i < h; i++) set(i, w - 1, cnt + 3);
for (int j = 0; j < w; j++) set(2, j, cnt + 3);
for (int j = 0; j < w; j++) set(0, j, cnt + 1);
for (int i = 0; i < h; i++) set(i, 0, cnt + 2);
for (int j = 0; j < w - 2; j++) set(1, j, cnt + 2);
set(1, w - 2, cnt + 1);
cnt += 3;
calc(h - 3, w - 2, (i, j, v) => set(i + 3, j + 1, v));
}
else if (h >= 4 && f[h - 4, w])
{
for (int i = 0; i < h - 1; i++) set(i, 0, cnt + 1);
for (int j = 0; j < w - 2; j++) set(1, j, cnt + 1);
for (int j = 1; j < w; j++) set(0, j, cnt + 2);
for (int i = 0; i < h - 2; i++) set(i, w - 2, cnt + 2);
for (int i = 1; i < h; i++) set(i, w - 1, cnt + 3);
for (int j = 2; j < w; j++) set(h - 2, j, cnt + 3);
for (int j = 0; j < w - 1; j++) set(h - 1, j, cnt + 4);
for (int i = 2; i < h; i++) set(i, 1, cnt + 4);
cnt += 4;
}
else
{
calc(w, h, (i, j, v) => set(j, i, v));
}
}
calc(h, w, (i, j, v) => a[i, j] = v);
if (cnt < 0)
{
Write(-1);
while (true) { }
}
else
{
Write(cnt);
WriteMat(a);
}
}
void CalcCT(int h, int w)
{
var a = new int[h, w];
int cnt = 0;
void calc(int h, int w, Action<int, int, int> set)
{
if (h <= 2 || w <= 2)
{
cnt = -IINF;
return;
}
if (h > w)
{
calc(w, h, (i, j, v) => set(j, i, v));
return;
}
if (h == 3)
{
for (int j = 0; j < w; j++)
{
set(0, j, cnt + 1);
set(1, j, cnt + 2);
set(2, j, cnt + 1);
}
set(0, w - 1, cnt + 2);
set(1, 0, cnt + 1);
set(2, w - 1, cnt + 2);
cnt += 2;
}
else if (h == 4)
{
for (int j = 0; j < w; j++)
{
set(0, j, cnt + 1);
set(1, j, cnt + 2);
set(2, j, cnt + 3);
set(3, j, cnt + 2);
}
set(1, w - 2, cnt + 1);
set(1, w - 1, cnt + 3);
set(2, 0, cnt + 2);
set(3, w - 1, cnt + 3);
cnt += 3;
}
else
{
for (int j = 0; j < w; j++) set(0, j, cnt + 1);
for (int i = 0; i < h; i++) set(i, 0, cnt + 1);
for (int j = 0; j < w; j++) set(h - 1, j, cnt + 1);
cnt += 1;
calc(h - 2, w - 1, (i, j, v) => set(i + 1, j + 1, v));
}
}
calc(h, w, (i, j, v) => a[i, j] = v);
if (cnt < 0)
{
Write(-1);
}
else
{
Write(cnt);
WriteMat(a);
}
}
#pragma warning disable CS0162, CS8618
public Solver() { if (!MultiTestCase) Solve(); else for (int t = ri; t > 0; t--) Solve(); }
#pragma warning restore CS0162, CS8618
const int IINF = 1 << 30;
const long INF = 1L << 60;
int ri { [MethodImpl(256)] get => (int)sc.Integer(); }
long rl { [MethodImpl(256)] get => sc.Integer(); }
uint rui { [MethodImpl(256)] get => (uint)sc.UInteger(); }
ulong rul { [MethodImpl(256)] get => sc.UInteger(); }
double rd { [MethodImpl(256)] get => sc.Double(); }
string rs { [MethodImpl(256)] get => sc.Scan(); }
string rline { [MethodImpl(256)] get => sc.Line(); }
public StreamScanner sc = new StreamScanner(Console.OpenStandardInput());
void ReadArray(out int[] a, int n) { a = new int[n]; for (int i = 0; i < a.Length; i++) a[i] = ri; }
void ReadArray(out long[] a, int n) { a = new long[n]; for (int i = 0; i < a.Length; i++) a[i] = rl; }
void ReadArray<T>(out T[] a, int n, Func<T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(); }
void ReadArray<T>(out T[] a, int n, Func<int, T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(i); }
}
static class Program
{
static public void Main(string[] args)
{
SourceExpander.Expander.Expand();
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
new Solver();
Console.Out.Flush();
}
}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace Lib { public partial class StreamScanner { public StreamScanner(Stream stream) { str = stream; } private readonly Stream str; private readonly byte[] buf = new byte[1024]; private int len, ptr; public bool isEof = false; public bool IsEndOfStream { get { return isEof; } } [MethodImpl(256)] private byte Read() { if (isEof) throw new EndOfStreamException(); if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } } return buf[ptr++]; } [MethodImpl(256)] public char Char() { byte b; do b = Read(); while (b < 33 || 126 < b); return (char)b; } [MethodImpl(256)] public string Line() { var sb = new StringBuilder(); for (var b = Char(); b != 10 && !isEof; b = (char)Read()) sb.Append(b); return sb.ToString(); } [MethodImpl(256)] public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)Read()) sb.Append(b); return sb.ToString(); } [MethodImpl(256)] public long Integer() { long ret = 0; var ng = false; byte b; do b = Read(); while (b != '-' && (b < '0' || '9' < b)); if (b == '-') { ng = true; b = Read(); } for (; '0' <= b && b <= '9'; b = Read()) ret = ret * 10 + (b ^ '0'); return ng ? -ret : ret; } [MethodImpl(256)] public ulong UInteger() { ulong ret = 0; byte b; do b = Read(); while (b < '0' || '9' < b); for (; '0' <= b && b <= '9'; b = Read()) ret = ret * 10 + (ulong)(b ^ '0'); return ret; } [MethodImpl(256)] public double Double() => double.Parse(Scan()); } }
namespace Lib { public static class OutputLib { [MethodImpl(256)] public static void WriteJoin<T>(string s, IEnumerable<T> t) => Console.WriteLine(string.Join(s, t)); [MethodImpl(256)] public static void WriteMat<T>(T[,] a, string sep = " ") { int sz1 = a.GetLength(0), sz2 = a.GetLength(1); var b = new T[sz2]; for (int i = 0; i < sz1; i++) { for (int j = 0; j < sz2; j++) b[j] = a[i, j]; WriteJoin(sep, b); } } [MethodImpl(256)] public static void WriteMat<T>(T[][] a, string sep = " ") { foreach (var ar in a) WriteJoin(sep, ar); } [MethodImpl(256)] public static void WriteMat<T>(T[][] a, Func<T, string> map, string sep = " ") { foreach (var ar in a) WriteJoin(sep, ar.Select(x => map(x))); } [MethodImpl(256)] public static void Write(object t) => Console.WriteLine(t.ToString()); [MethodImpl(256)] public static void Write(params object[] arg) => Console.WriteLine(string.Join(" ", arg.Select(x => x.ToString()))); [MethodImpl(256)] public static void Write(string str) => Console.WriteLine(str); [MethodImpl(256)] public static void WriteFlush(object t) { Console.WriteLine(t.ToString()); Console.Out.Flush(); } [MethodImpl(256)] public static void WriteError(object t) => Console.Error.WriteLine(t.ToString()); [MethodImpl(256)] public static void Flush() => Console.Out.Flush(); [MethodImpl(256)] public static void YN(bool t) => Console.WriteLine(t ? "YES" : "NO"); [MethodImpl(256)] public static void Yn(bool t) => Console.WriteLine(t ? "Yes" : "No"); [MethodImpl(256)] public static void yn(bool t) => Console.WriteLine(t ? "yes" : "no"); [MethodImpl(256)] public static void DeleteLine() => Console.Write("\x1b[1A\x1b[2K"); [MethodImpl(256)] public static void ProgressBar(long now, long total, int blocks = 50) { int x = (int)((2 * now * blocks + 1) / (2 * total)); Console.Write($"\x1b[G[\x1b[42m{string.Concat(Enumerable.Repeat("_", x))}\x1b[0m{string.Concat(Enumerable.Repeat("_", blocks - x))}] : {now} / {total}"); } } }
namespace SourceExpander { public class Expander { [Conditional("EXP")] public static void Expand(string inputFilePath = null, string outputFilePath = null, bool ignoreAnyError = true) { } public static string ExpandString(string inputFilePath = null, bool ignoreAnyError = true) { return ""; } } }
#endregion Expanded by https://github.com/kzrnm/SourceExpander