結果
| 問題 |
No.184 たのしい排他的論理和(HARD)
|
| コンテスト | |
| ユーザー |
 utaka
|
| 提出日時 | 2019-09-27 20:15:47 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,876 bytes |
| コンパイル時間 | 2,487 ms |
| コンパイル使用メモリ | 119,492 KB |
| 実行使用メモリ | 49,596 KB |
| 最終ジャッジ日時 | 2024-07-04 12:31:46 |
| 合計ジャッジ時間 | 7,004 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 WA * 22 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
#if true && UTAKA_LOCAL
//#if false
#define UTAKA_DEBUG
#endif
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.IO;
using System.Linq;
using System.Net.Mime;
using System.Text;
namespace UtakaApp
{
public partial class Program
{
public const string SiteName = "Yukicoder";
public const string ContestName = "184";
public const string ProblemName = "";
public static void Main(string[] args)
{
#if UTAKA_LOCAL
//#if false
new TestCaseCheckerForAtCoder().TestProblems();
#else
var console = new MyConsole();
new Program().Solve(System.Console.In, console);
console.Flush();
#endif
var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
}
public void Solve(TextReader textReader, IConsole console)
{
var cin = new ConsoleInput(textReader);
int N = cin.ReadInt;
long[] A = cin.ReadLongArray(N);
int rank = GaussJordanBit.CalcReverse(A, 61, false);
long x = 0;
var ans = Math.Pow(2, rank);
console.WriteLine(ans.ToString());
}
long LongMax(long x, long y)
{
return (x > y) ? x : y;
}
[Conditional("UTAKA_DEBUG")]
public void DebugWriteEnumerable<T>(IEnumerable<T> A, string delimiter = " ")
{
var sb = new StringBuilder();
foreach (T v in A)
{
sb.Append(v);
sb.Append(" ");
}
if (sb.Length > 0)
{
sb.Length--;
}
Console.WriteLine(sb.ToString());
}
}
/// 0 1 の掃き出し法
public static class GaussJordanBit
{
/// 桁の大きい方から掃き出す
/// rankを返す
public static int CalcReverse(long[] A, int n, bool isExtended = false)
{
int m = A.Length;
int rank = 0;
for (int col = n; col >= 0; col--)
{
if (isExtended && col == 0) break;
int pivot = -1;
for (int row = rank; row < m; row++)
{
if ((A[row] & 1L << col) != 0)
{
pivot = row;
break;
}
}
if (pivot == -1) continue;
Swap(ref A[pivot], ref A[rank]);
for (int row = 0; row < m; row++)
{
if (row != rank && (A[row] & 1L << col) != 0)
{
A[row] ^= A[rank];
}
}
rank++;
}
return rank;
}
public static int LinearEquationReverse(long[] inputA, bool[] b, int n, out bool[] result)
{
int m = inputA.Length;
// 拡張する ただしinputAに1列分の余裕が必要
long[] A = new long[m];
for (int row = 0; row < m; row++)
{
A[row] |= (A[row] << 1) & (b[row] ? 1 : 0);
}
// out引数に値を入れておく
result = new bool[m];
// 解があるか求める
int rank = CalcReverse(A, n, true);
for (int row = rank; row < m; row++)
{
if ((A[row] & 1) > 0) return -1;
}
// 解を求める
for (int row = 0; row < rank; row++)
{
result[row] = (A[row] & 1) != 0;
}
return rank;
}
/// 掃き出す
/// rankを返す
public static int Calc(long[] A, int n, bool isExtended = false)
{
int m = A.Length;
int rank = 0;
for (int col = 0; col < n; col++)
{
if (isExtended && col == n - 1) break;
int pivot = -1;
for (int row = rank; row < m; row++)
{
if ((A[row] & 1L << col) != 0)
{
pivot = row;
break;
}
}
if (pivot == -1) continue;
Swap(ref A[pivot], ref A[rank]);
for (int row = 0; row < m; row++)
{
if (row != rank && (A[row] & 1L << col) != 0)
{
A[row] ^= A[rank];
}
}
rank++;
}
return rank;
}
public static int LinearEquation(long[] inputA, bool[] b, int n, out bool[] result)
{
int m = inputA.Length;
// 拡張する ただしinputAに1列分の余裕が必要
long[] A = new long[m];
for (int row = 0; row < m; row++)
{
if (b[row])
{
A[row] |= 1L << n;
}
}
// out引数に値を入れておく
result = new bool[m];
// 解があるか求める
int rank = Calc(A, n, true);
for (int row = rank; row < m; row++)
{
if ((A[row] & 1L << n) > 0) return -1;
}
// 解を求める
for (int row = 0; row < rank; row++)
{
result[row] = (A[row] & 1L << n) != 0;
}
return rank;
}
public static void Swap<T>(ref T a, ref T b)
{
T c = a;
a = b;
b = c;
}
}
public partial class Program
{
public const int ModLarge = 1000000007;
}
public class ConsoleInput
{
private readonly TextReader _stream;
private readonly char _separator = ' ';
private readonly Queue<string> inputStream;
public ConsoleInput(TextReader stream, char separator = ' ')
{
_separator = separator;
_stream = stream;
inputStream = new Queue<string>();
}
public string Read
{
get
{
if (inputStream.Count != 0)
{
return inputStream.Dequeue();
}
var tmp = _stream.ReadLine().Split(_separator);
for (var i = 0; i < tmp.Length; ++i)
{
inputStream.Enqueue(tmp[i]);
}
return inputStream.Dequeue();
}
}
public string ReadLine => _stream.ReadLine();
public int ReadInt => int.Parse(Read);
public long ReadLong => long.Parse(Read);
public double ReadDouble => double.Parse(Read);
public string[] ReadStrArray(long N)
{
var ret = new string[N];
for (long i = 0; i < N; ++i)
{
ret[i] = Read;
}
return ret;
}
public int[] ReadIntArray(long N)
{
var ret = new int[N];
for (long i = 0; i < N; ++i)
{
ret[i] = ReadInt;
}
return ret;
}
public long[] ReadLongArray(long N)
{
var ret = new long[N];
for (long i = 0; i < N; ++i)
{
ret[i] = ReadLong;
}
return ret;
}
}
public interface IConsole
{
void Flush();
void Write(string str);
void WriteLine(string str);
}
public class MyConsole : IConsole
{
public MyConsole()
{
var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
Console.SetOut(sw);
}
public void Flush()
{
Console.Out.Flush();
}
public void Write(string str)
{
Console.Write(str);
}
public void WriteLine(string str)
{
Console.WriteLine(str);
}
}
#if UTAKA_LOCAL
public class DebugConsole : IConsole
{
private readonly StringBuilder mSb;
public DebugConsole()
{
mSb = new StringBuilder();
}
public void Flush()
{
// 何もしない
}
public void Write(string str)
{
mSb.Append(str);
}
public void WriteLine(string str)
{
mSb.AppendLine(str);
}
public string GetAllOutput()
{
return mSb.ToString();
}
}
#endif
#if UTAKA_LOCAL
public class TestCaseCheckerForAtCoder
{
private string GetDirectoryPath()
{
var problemPart = string.IsNullOrEmpty(Program.ProblemName)
? ""
: $"/{Program.ProblemName}";
return
$"{System.Environment.GetFolderPath(Environment.SpecialFolder.UserProfile)}/AlgorithmPrac/{Program.SiteName}/{Program.ContestName}{problemPart}";
}
private string GetInputFilePath(int testCaseNumber)
{
return $"{GetDirectoryPath()}/sample-{testCaseNumber}.in";
}
private string GetOutputFilePath(int testCaseNumber)
{
return $"{GetDirectoryPath()}/sample-{testCaseNumber}.out";
}
public bool TestProblem(int testCaseNumber)
{
var inputFilePath = GetInputFilePath(testCaseNumber);
var outputFilePath = GetOutputFilePath(testCaseNumber);
TextReader inputStream = new StreamReader(inputFilePath);
var debugConsoleWriter = new DebugConsole();
new Program().Solve(inputStream, debugConsoleWriter);
var output = debugConsoleWriter.GetAllOutput();
TextReader outputStream = new StreamReader(outputFilePath);
var outputAnswer = outputStream.ReadToEnd();
Dbg.WriteLine(output);
Dbg.WriteLine(outputAnswer);
var isCorrect = output == outputAnswer;
return isCorrect;
}
public void TestProblems()
{
var isSuccessAll = true;
var testCaseNumber = 1;
while (true)
{
var inputFileName = GetInputFilePath(testCaseNumber);
if (!File.Exists(inputFileName))
{
break;
}
Console.WriteLine($"TestCase {testCaseNumber} =====================================================");
var result = TestProblem(testCaseNumber);
if (result)
{
Console.WriteLine("Success");
}
else
{
isSuccessAll = false;
Console.WriteLine("Failure *****");
}
testCaseNumber++;
}
if (isSuccessAll)
{
Console.WriteLine("!!!!!!!!! All Success !!!!!!!!!");
}
}
}
#endif
#if UTAKA_LOCAL
public static class Dbg
{
public static void WriteLine(string str)
{
Console.WriteLine(str);
}
public static void Write(string str)
{
Console.Write(str);
}
}
#else
public static class Dbg
{
public static void WriteLine(string str)
{
}
public static void Write(string str)
{
}
}
#endif
}