結果
| 問題 | No.142 単なる配列の操作に関する実装問題 |
| ユーザー |
 紙ぺーぱー
|
| 提出日時 | 2018-03-03 22:42:03 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,823 bytes |
| コンパイル時間 | 6,467 ms |
| コンパイル使用メモリ | 111,788 KB |
| 実行使用メモリ | 33,420 KB |
| 最終ジャッジ日時 | 2023-09-18 05:35:54 |
| 合計ジャッジ時間 | 15,034 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Linq;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using SB = System.Text.StringBuilder;
using Number = System.Int64;
namespace Program {
public class Solver {
Random rnd = new Random(0);
public void Solve() {
var n = ri;
var s = rl; var x = rl; var y = rl; var z = rl;
var set = new bitset(n);
{
set[0] = s % 2 == 1;
for (int i = 1; i < n; i++)
{
s = (s * x + y) % z;
set[i] = s % 2 == 1;
}
}
var q = ri;
for (int i = 0; i < q; i++)
{
var l1 = ri - 1; var r1 = ri;
var l2 = ri - 1; var r2 = ri;
set.ApplyXOR(set, l2, r1 - l1, l1);
}
for (int i = 0; i < n; i++)
if (set[i]) Console.Write('O');
else Console.Write('E');
Console.WriteLine();
}
const long INF = 1L << 60;
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };
int ri { get { return sc.Integer(); } }
long rl { get { return sc.Long(); } }
double rd { get { return sc.Double(); } }
string rs { get { return sc.Scan(); } }
public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
static T[] Enumerate<T>(int n, Func<int, T> f) {
var a = new T[n];
for (int i = 0; i < n; ++i) a[i] = f(i);
return a;
}
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}
}
#region main
static class Ex {
static public string AsString(this IEnumerable<char> ie) { return new string(ie.ToArray()); }
static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") {
return string.Join(st, ie);
}
static public void Main() {
Console.SetOut(new Program.IO.Printer(Console.OpenStandardOutput()) { AutoFlush = false });
var solver = new Program.Solver();
try
{
solver.Solve();
Console.Out.Flush();
}
catch { }
}
}
#endregion
#region Ex
namespace Program.IO {
using System.IO;
using System.Text;
using System.Globalization;
public class Printer: StreamWriter {
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
}
public class StreamScanner {
public StreamScanner(Stream stream) { str = stream; }
public readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
public bool IsEndOfStream { get { return isEof; } }
private byte read() {
if (isEof) return 0;
if (ptr >= len)
{
ptr = 0;
if ((len = str.Read(buf, 0, 1024)) <= 0)
{
isEof = true;
return 0;
}
}
return buf[ptr++];
}
public char Char() {
byte b = 0;
do b = read(); while ((b < 33 || 126 < b) && !isEof);
return (char)b;
}
public string Scan() {
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b);
return sb.ToString();
}
public string ScanLine() {
var sb = new StringBuilder();
for (var b = Char(); b != '\n' && b != 0; b = (char)read()) if (b != '\r') sb.Append(b);
return sb.ToString();
}
public long Long() { return isEof ? long.MinValue : long.Parse(Scan()); }
public int Integer() { return isEof ? int.MinValue : int.Parse(Scan()); }
public double Double() { return isEof ? double.NaN : double.Parse(Scan(), CultureInfo.InvariantCulture); }
}
}
#endregion
public class bitset {
const int B = 64;
static readonly ulong[] mask = new ulong[65];
static readonly ulong[] revmask = new ulong[65];
static readonly ulong[] cache = new ulong[1000000];
static bitset() {
mask[0] = 0;
for (int i = 0; i < 64; i++)
mask[i + 1] = (mask[i] << 1) | 1ul;
for (int i = 0; i < 65; i++)
revmask[i] = ~mask[i];
}
static void align(ref int l1, int l2, ref int len, int m1) {
if (l1 < 0) { l2 += Math.Abs(l1); len -= Math.Abs(l1); l1 = 0; }
len = Math.Min(m1 - l1, len);
}
int n;
ulong[] bits;
public bitset(int N) {
n = N;
bits = new ulong[n / B + 2];
}
public bool this[int index] {
get { return (bits[index / B] >> index & 1) == 1; }
set {
if (value)
bits[index / B] |= 1ul << index;
else bits[index / B] &= ~(1ul << index);
}
}
/// <summary>
/// this[l1,l1+len) &= mask[l2,l2+len)
/// </summary>
public void ApplyAND(bitset Mask, int l1, int len, int l2 = 0) {
align(ref l1, l2, ref len, n);
align(ref l2, l1, ref len, Mask.n);
int lx = l1 / B, ly = l1 % B, rx = (l1 + len) / B, ry = (l1 + len) % B;
var dx = (l2 - l1) / B;
var dy = (l2 - l1) % B;
if (dy < 0) { dy += B; dx--; }
var revdy = (B - dy) % B;
for (int i = lx; i <= rx; i++)
cache[i] = (i + dx < 0 ? 0 : Mask.bits[i + dx] >> dy) | (revdy == 0 ? 0 : Mask.bits[i + dx + 1] << revdy);
if (lx == rx) bits[lx] &= cache[lx] | ~(mask[ry] & revmask[ly]);
else
{
bits[lx] &= cache[lx] | ~revmask[ly];
for (int i = lx + 1; i < rx; i++)
bits[lx] &= cache[i];
bits[rx] &= cache[rx] | ~mask[ry];
}
}
/// <summary>
/// this[l1,l1+len) |= mask[l2,l2+len)
/// </summary>
public void ApplyOR(bitset Mask, int l1, int len, int l2 = 0) {
align(ref l1, l2, ref len, n);
align(ref l2, l1, ref len, Mask.n);
int lx = l1 / B, ly = l1 % B, rx = (l1 + len) / B, ry = (l1 + len) % B;
var dx = (l2 - l1) / B;
var dy = (l2 - l1) % B;
if (dy < 0) { dy += B; dx--; }
var revdy = (B - dy) % B;
for (int i = lx; i <= rx; i++)
cache[i] = (i + dx < 0 ? 0 : Mask.bits[i + dx] >> dy) | (revdy == 0 ? 0 : Mask.bits[i + dx + 1] << revdy);
if (lx == rx) bits[lx] |= cache[lx] & (mask[ry] & revmask[ly]);
else
{
bits[lx] |= cache[lx] & revmask[ly];
for (int i = lx + 1; i < rx; i++)
bits[lx] |= cache[i];
bits[rx] |= cache[rx] & mask[ry];
}
}
/// <summary>
/// this[l1,l1+len) ^= mask[l2,l2+len)
/// </summary>
public void ApplyXOR(bitset Mask, int l1, int len, int l2 = 0) {
align(ref l1, l2, ref len, n);
align(ref l2, l1, ref len, Mask.n);
int lx = l1 / B, ly = l1 % B, rx = (l1 + len) / B, ry = (l1 + len) % B;
var dx = (l2 - l1) / B;
var dy = (l2 - l1) % B;
if (dy < 0) { dy += B; dx--; }
var revdy = (B - dy) % B;
for (int i = lx; i <= rx; i++)
cache[i] = (i + dx < 0 ? 0 : Mask.bits[i + dx] >> dy) | (revdy == 0 ? 0 : Mask.bits[i + dx + 1] << revdy);
if (lx == rx) bits[lx] ^= cache[lx] & (mask[ry] & revmask[ly]);
else
{
bits[lx] ^= cache[lx] & revmask[ly];
for (int i = lx + 1; i < rx; i++)
bits[lx] ^= cache[i];
bits[rx] ^= cache[rx] & mask[ry];
}
}
}