結果
| 問題 |
No.3335 ReCT
|
| コンテスト | |
| ユーザー |
 KumaTachiRen
|
| 提出日時 | 2025-11-07 23:53:39 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 14,997 bytes |
| コンパイル時間 | 8,483 ms |
| コンパイル使用メモリ | 169,472 KB |
| 実行使用メモリ | 992,140 KB |
| 最終ジャッジ日時 | 2025-11-07 23:53:52 |
| 合計ジャッジ時間 | 12,261 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 10 MLE * 1 -- * 86 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (146 ミリ秒)。 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.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 && j >= 3) f[i, j] |= f[i - 4, j];
if (i >= 6 && j >= 3) f[i, j] |= f[i - 6, j];
if (i >= 3 && j >= 4) f[i, j] |= f[i, j - 4];
if (i >= 3 && j >= 6) f[i, j] |= f[i, j - 6];
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];
}
// WriteMat(f);
var a = new int[h, w];
int x0 = 0, y0 = 0;
bool flip = false;
void set(int i, int j, int v)
{
if (flip) a[x0 + j, y0 + i] = v;
else a[x0 + i, y0 + j] = v;
}
void shift(int i, int j)
{
if (flip) { x0 += j; y0 += i; }
else { x0 += i; y0 += j; }
}
int cnt = 0;
void calc(int h, int w)
{
if (h == 0 || w == 0) return;
if (!f[h, w])
{
cnt = -IINF;
return;
}
if (h >= 4 && w >= 3 && f[h - 4, w])
{
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;
shift(4, 0);
calc(h - 4, w);
}
else if (h >= 4 && w >= 3 && f[h - 4, w])
{
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;
shift(6, 0);
calc(h - 6, w);
}
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;
shift(1, 1);
calc(h - 1, w - 2);
}
else
{
flip = !flip;
calc(w, h);
}
}
calc(h, w);
if (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 >= 5 && j >= 5) f[i, j] |= f[i - 5, j];
if (i >= 5 && j >= 5) f[i, j] |= f[i, j - 5];
if (i >= 6 && j >= 5) f[i, j] |= f[i - 6, j];
if (i >= 5 && j >= 6) f[i, j] |= f[i, j - 6];
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];
}
// WriteMat(f);
var a = new int[h, w];
int cnt = 0;
int x0 = 0, y0 = 0;
bool flip = false;
void set(int i, int j, int v)
{
if (flip) a[x0 + j, y0 + i] = v;
else a[x0 + i, y0 + j] = v;
}
void shift(int i, int j)
{
if (flip) { x0 += j; y0 += i; }
else { x0 += i; y0 += j; }
}
void calc(int h, int w)
{
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;
shift(3, 1);
calc(h - 3, w - 2);
}
else if (h >= 4 && w >= 4 && f[h - 4, w])
{
for (int i = 0; i < 4; i++)
for (int j = 0; j < w; j++)
set(i, j, cnt + 1 + i);
set(1, w - 2, cnt + 1);
set(0, 0, cnt + 2);
set(2, 0, cnt + 2);
set(1, w - 1, cnt + 3);
set(3, w - 1, cnt + 3);
set(2, 1, cnt + 4);
cnt += 4;
shift(4, 0);
calc(h - 4, w);
}
else if (h >= 5 && w >= 5 && f[h - 5, w])
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < w; j++)
set(i, j, cnt + 1 + i);
set(1, 1, cnt + 1);
set(2, w - 2, cnt + 2);
set(1, 0, cnt + 3);
set(3, 0, cnt + 3);
set(2, w - 1, cnt + 4);
set(4, w - 1, cnt + 4);
set(3, 1, cnt + 5);
cnt += 5;
shift(5, 0);
calc(h - 5, w);
}
else if (h >= 6 && w >= 5 && f[h - 6, w])
{
for (int i = 0; i < 6; i++)
for (int j = 0; j < w; j++)
set(i, j, cnt + 1 + i);
for (int i = 0; i < 5; i++) set(i, w - 1, cnt + 2);
for (int i = 1; i < 6; i++) set(i, 0, cnt + 5);
set(1, 1, cnt + 1);
set(1, 2, cnt + 3);
set(4, w - 3, cnt + 4);
set(4, w - 2, cnt + 6);
cnt += 6;
shift(6, 0);
calc(h - 6, w);
}
else
{
flip = !flip;
calc(w, h);
}
}
calc(h, w);
if (cnt < 0)
{
Write(-1);
}
else
{
Write(cnt);
WriteMat(a);
}
}
void CalcCT(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 == 3 || i == 4) && j >= 3) f[i, j] = true;
if (i >= 3 && (j == 3 || j == 4)) 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];
}
// WriteMat(f);
var a = new int[h, w];
int cnt = 0;
int x0 = 0, y0 = 0;
bool flip = false;
void set(int i, int j, int v)
{
if (flip) a[x0 + j, y0 + i] = v;
else a[x0 + i, y0 + j] = v;
}
void shift(int i, int j)
{
if (flip) { x0 += j; y0 += i; }
else { x0 += i; y0 += j; }
}
void calc(int h, int w)
{
if (h == 0 || w == 0) return;
if (!f[h, w])
{
cnt = -IINF;
return;
}
if (h > w)
{
flip = !flip;
calc(w, h);
}
else 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;
shift(1, 1);
calc(h - 2, w - 1);
}
}
calc(h, w);
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