結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 iwkjosec
|
| 提出日時 | 2018-06-01 13:59:16 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 825 ms / 1,000 ms |
| コード長 | 8,551 bytes |
| コンパイル時間 | 31,401 ms |
| 実行使用メモリ | 18,092 KB |
| スコア | 41,301 |
| 最終ジャッジ日時 | 2018-06-01 13:59:50 |
|
ジャッジサーバーID （参考情報） |
judge9 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 2.3.1.61919 (57c81319) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
class Program
{
static void Main()
{
var dt = DateTime.Now;
ReadLine();
var N = 60;
var K = 500;
var L = ReadLine().Split().Select(int.Parse).ToArray();
var map = new bool[N, N];
for (int i = 0; i < N; i++)
{
var line = ReadLine();
for (int j = 0; j < N; j++)
{
map[i, j] = line[j] == '0';
}
}
var W0 = CalcW0(map);
var Wk = 0;
var cmd = new int[K, 4];
for (int k = 0; k < K; k++)
{
var x = 0;
var a = 0;
var b = 0;
var c = 0;
var d = 0;
for (int i = 0; i < N; i++)
{
var n = 0;
for (int l = 0; l < L[k]; l++)
{
n += map[i, l] ? 0 : 1;
}
if (x < n)
{
x = n;
a = c = i;
b = 0;
d = L[k] - 1;
}
for (int j = 0; j < N - L[k]; j++)
{
n -= map[i, j] ? 0 : 1;
n += map[i, j + L[k]] ? 0 : 1;
if (x < n)
{
x = n;
a = c = i;
b = j + 1;
d = j + L[k];
}
}
}
for (int j = 0; j < N; j++)
{
var n = 0;
for (int l = 0; l < L[k]; l++)
{
n += map[l, j] ? 0 : 1;
}
if (x < n)
{
x = n;
b = d = j;
a = 0;
c = L[k] - 1;
}
for (int i = 0; i < N - L[k]; i++)
{
n -= map[i, j] ? 0 : 1;
n += map[i + L[k], j] ? 0 : 1;
if (x < n)
{
x = n;
b = d = j;
a = i + 1;
c = i + L[k];
}
}
}
cmd[k, 0] = a;
cmd[k, 1] = b;
cmd[k, 2] = c;
cmd[k, 3] = d;
Act(map, a, b, c, d);
}
Wk = Score(map, W0);
var ct = 0;
var r = new XorShift();
while ((DateTime.Now - dt).Milliseconds < 800)
{
var k = ct % K;
Act(map, cmd[k, 0], cmd[k, 1], cmd[k, 2], cmd[k, 3]);
var x = 0;
var a = 0;
var b = 0;
var c = 0;
var d = 0;
for (int i = 0; i < N; i++)
{
var n = 0;
for (int l = 0; l < L[k]; l++)
{
n += map[i, l] ? 0 : 1;
}
if (x < n)
{
x = n;
a = c = i;
b = 0;
d = L[k] - 1;
}
for (int j = 0; j < N - L[k]; j++)
{
n -= map[i, j] ? 0 : 1;
n += map[i, j + L[k]] ? 0 : 1;
if (x < n)
{
x = n;
a = c = i;
b = j + 1;
d = j + L[k];
}
}
}
for (int j = 0; j < N; j++)
{
var n = 0;
for (int l = 0; l < L[k]; l++)
{
n += map[l, j] ? 0 : 1;
}
if (x < n)
{
x = n;
b = d = j;
a = 0;
c = L[k] - 1;
}
for (int i = 0; i < N - L[k]; i++)
{
n -= map[i, j] ? 0 : 1;
n += map[i + L[k], j] ? 0 : 1;
if (x < n)
{
x = n;
b = d = j;
a = i + 1;
c = i + L[k];
}
}
}
cmd[k, 0] = a;
cmd[k, 1] = b;
cmd[k, 2] = c;
cmd[k, 3] = d;
Act(map, a, b, c, d);
ct++;
}
for (int i = 0; i < K; i++)
{
var a = cmd[i, 0];
var b = cmd[i, 1];
var c = cmd[i, 2];
var d = cmd[i, 3];
WriteLine($"{a + 1} {b + 1} {c + 1} {d + 1}");
}
Error.WriteLine(ct);
Error.WriteLine(Score(map, W0));
Error.WriteLine(32 * Score(map, W0));
}
static int CalcW0(bool[,] map)
{
var W0 = 0;
for (int i = 0; i < 60; i++)
{
for (int j = 0; j < 60; j++)
{
if (map[i, j]) W0++;
}
}
return W0;
}
static void Act(bool[,] map, int a, int b, int c, int d)
{
if (a == c)
{
var x = Math.Min(b, d);
var r = x + Math.Abs(b - d) + 1;
for (int j = x; j < r; j++)
{
map[a, j] = !map[a, j];
}
}
else
{
var y = Math.Min(a, c);
var r = y + Math.Abs(a - c) + 1;
for (int j = y; j < r; j++)
{
map[j, b] = !map[j, b];
}
}
}
static int Score(bool[,] map, int W0)
{
var t = 0;
for (int i = 0; i < 60; i++)
{
for (int j = 0; j < 60; j++)
{
if (map[i, j]) t++;
}
}
return t - W0;
}
static bool WillBeGood(bool[,] map, int a, int b, int c, int d, int A, int B, int C, int D)
{
if (a == c)
{
if (a == A)
{
var k = WhiteCount(map, a, Math.Min(b, B), c, Math.Min(b, B) + Math.Abs(b - B) - 1);
var w = WhiteCount(map, a, Math.Min(d, D) + 1, c, Math.Min(d, D) + Math.Abs(d - D));
return Math.Abs(b - B) > k + w;
}
else
{
var k = WhiteCount(map, a, b, c, d);
var w = WhiteCount(map, A, B, C, D);
return Math.Abs(b - d) + 1 > k + w;
}
}
else
{
if (b == B)
{
var k = WhiteCount(map, Math.Min(a, A), b, Math.Min(a, A) + Math.Abs(a - A) - 1, d);
var w = WhiteCount(map, Math.Min(c, C) + 1, b, Math.Min(c, C) + Math.Abs(c - C), d);
return Math.Abs(a - A) > k + w;
}
else
{
var k = WhiteCount(map, a, b, c, d);
var w = WhiteCount(map, A, B, C, D);
return Math.Abs(a - c) + 1 > k + w;
}
}
}
static int WhiteCount(bool[,] map, int a, int b, int c, int d)
{
var w = 0;
if (a == c)
{
var x = Math.Min(b, d);
var r = x + Math.Abs(b - d) + 1;
for (int j = x; j < r; j++)
{
if (map[a, j]) w++;
}
return w;
}
else
{
var y = Math.Min(a, c);
var r = y + Math.Abs(a - c) + 1;
for (int j = y; j < r; j++)
{
if (map[j, b]) w++;
}
return w;
}
}
}
public class XorShift
{
uint x = 123456789;
uint y = 362436069;
uint z = 521288629;
uint w = 88675123;
public XorShift()
{
var t = (uint)Environment.TickCount;
x ^= t;
y ^= Shift(t, 17);
z ^= Shift(t, 31);
w ^= Shift(t, 18);
}
uint Shift(uint u, int n) => u << n | u >> 32 - n;
public int Next()
{
var t = x ^ x << 11;
x = y; y = z; z = w;
t = w = w ^ w >> 19 ^ t ^ t >> 8;
if (t > int.MaxValue) t = ~t;
return (int)(t == int.MaxValue ? --t : t);
}
public int Next(int maxValue) => (int)(NextDouble() * maxValue);
public double NextDouble() => (double)Next() / int.MaxValue;
}