結果
| 問題 |
No.1959 Prefix MinMax
|
| コンテスト | |
| ユーザー |
 cotton_fn_
|
| 提出日時 | 2022-05-28 12:38:39 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 20,852 bytes |
| コンパイル時間 | 13,135 ms |
| コンパイル使用メモリ | 396,148 KB |
| 実行使用メモリ | 25,476 KB |
| 平均クエリ数 | 42.28 |
| 最終ジャッジ日時 | 2024-09-20 21:24:58 |
| 合計ジャッジ時間 | 19,212 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 7 RE * 24 |
ソースコード
#![allow(unused_imports)]
use input::*;
use std::{
collections::*,
io::{self, BufWriter, Write},
};
fn run<I: Input, O: Write>(mut ss: I, mut out: O) {
use random::*;
let t: i32 = ss.parse();
let mut rng = Xoshiro::seed_from_u64(1959);
for _ in 0..t {
let n: usize = ss.parse();
let b: Vec<u32> = (0..n - 1)
.map(|_| loop {
let x: u32 = rng.range(0, 1 << 10);
if x.count_ones() == 5 {
break x;
}
})
.collect();
let mut ans = vec![0; n];
for q in 0..10 {
w!(out, "?");
for &b in &b {
w!(out, " {}", (b >> q) & 1);
}
wln!(out);
out.flush().unwrap();
let mut prev = 0;
for (a, ans) in ss.seq::<usize>().take(n).zip(&mut ans) {
if a != prev {
*ans = a;
}
prev = a;
}
}
w!(out, "!");
for ans in ans {
w!(out, " {}", ans);
}
wln!(out);
out.flush().unwrap();
}
}
fn main() {
let stdin = io::stdin();
let ss = SplitWs::new(stdin.lock());
let stdout = io::stdout();
let out = BufWriter::new(stdout.lock());
run(ss, out);
}
pub mod random {
mod pcg {
use super::{RngCore, SeedableRng};
#[doc = " PCG-XSH-RR"]
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Pcg(u64);
const MUL: u64 = 5129263795064623965;
const INC: u64 = 4280768313201238837;
impl SeedableRng for Pcg {
fn seed_from_u64(seed: u64) -> Self {
Self(seed.wrapping_add(INC))
}
}
impl RngCore for Pcg {
fn next_u32(&mut self) -> u32 {
let mut x = self.0;
self.0 = x.wrapping_mul(MUL).wrapping_add(INC);
x ^= x >> 18;
((x >> 27) as u32).rotate_right((x >> 59) as u32)
}
fn next_u64(&mut self) -> u64 {
(self.next_u32() as u64) << 32 | self.next_u32() as u64
}
}
}
mod xoshiro {
use super::{RngCore, SeedableRng};
#[doc = " <https://xoshiro.di.unimi.it/xoshiro256plusplus.c>"]
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Xoshiro([u64; 4]);
impl Xoshiro {
pub fn from_seed(seed: [u64; 4]) -> Self {
Self(seed)
}
}
impl SeedableRng for Xoshiro {
fn seed_from_u64(seed: u64) -> Self {
let mut sm = SplitMix::seed_from_u64(seed);
let mut state = [0; 4];
for s in &mut state {
*s = sm.next_u64();
}
Self::from_seed(state)
}
}
impl RngCore for Xoshiro {
fn next_u32(&mut self) -> u32 {
(self.next_u64() >> 32) as u32
}
fn next_u64(&mut self) -> u64 {
let res = (self.0[0].wrapping_add(self.0[3]))
.rotate_left(23)
.wrapping_add(self.0[0]);
let t = self.0[1] << 17;
self.0[2] ^= self.0[0];
self.0[3] ^= self.0[1];
self.0[1] ^= self.0[2];
self.0[0] ^= self.0[3];
self.0[2] ^= t;
self.0[3] = self.0[3].rotate_left(45);
res
}
}
#[doc = " <https://xoshiro.di.unimi.it/splitmix64.c>"]
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct SplitMix(u64);
impl SeedableRng for SplitMix {
fn seed_from_u64(seed: u64) -> Self {
Self(seed)
}
}
impl RngCore for SplitMix {
fn next_u32(&mut self) -> u32 {
(self.next_u64() >> 32) as u32
}
fn next_u64(&mut self) -> u64 {
self.0 = self.0.wrapping_add(0x9e3779b97f4a7c15);
let mut z = self.0;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
z ^ (z >> 31)
}
}
}
pub use self::pcg::Pcg;
pub use self::xoshiro::*;
pub trait RngCore {
fn next_u32(&mut self) -> u32;
fn next_u64(&mut self) -> u64;
}
pub trait Rng: RngCore {
fn gen<T: Sample>(&mut self) -> T {
T::sample(self)
}
fn range<T: Uniform>(&mut self, l: T, r: T) -> T {
T::range(self, l, r)
}
fn range_inclusive<T: Uniform>(&mut self, l: T, r: T) -> T {
T::range_inclusive(self, l, r)
}
fn gen_bool(&mut self, p: f64) -> bool {
if p >= 1. {
return true;
}
self.next_u64() < (2.0f64.powi(64) * p) as u64
}
fn open01<T: SampleFloat>(&mut self) -> T {
T::open01(self)
}
fn standard_normal<T: SampleFloat>(&mut self) -> T {
T::standard_normal(self)
}
fn normal<T: SampleFloat>(&mut self, mean: T, sd: T) -> T {
T::normal(self, mean, sd)
}
fn exp<T: SampleFloat>(&mut self, lambda: T) -> T {
T::exp(self, lambda)
}
fn shuffle<T>(&mut self, a: &mut [T]) {
for i in (1..a.len()).rev() {
a.swap(self.range_inclusive(0, i), i);
}
}
fn partial_shuffle<'a, T>(
&mut self,
a: &'a mut [T],
n: usize,
) -> (&'a mut [T], &'a mut [T]) {
let n = n.min(a.len());
for i in 0..n {
a.swap(i, self.range(i, a.len()));
}
a.split_at_mut(n)
}
fn choose<'a, T>(&mut self, a: &'a [T]) -> &'a T {
assert!(!a.is_empty());
&a[self.range(0, a.len())]
}
fn choose_mut<'a, T>(&mut self, a: &'a mut [T]) -> &'a mut T {
assert!(!a.is_empty());
&mut a[self.range(0, a.len())]
}
}
impl<T: RngCore> Rng for T {}
pub trait Sample {
fn sample<T: Rng + ?Sized>(rand: &mut T) -> Self;
}
pub trait Uniform {
fn range<T: Rng + ?Sized>(rand: &mut T, l: Self, r: Self) -> Self;
fn range_inclusive<T: Rng + ?Sized>(rand: &mut T, l: Self, r: Self) -> Self;
}
pub trait SampleFloat {
fn open01<T: Rng + ?Sized>(rand: &mut T) -> Self;
fn standard_normal<T: Rng + ?Sized>(rand: &mut T) -> Self;
fn normal<T: Rng + ?Sized>(rand: &mut T, mean: Self, sd: Self) -> Self;
fn exp<T: Rng + ?Sized>(rand: &mut T, lambda: Self) -> Self;
}
macro_rules ! int_impl { ($ ($ type : ident) ,*) => { $ (impl Sample for $ type { fn sample < T : Rng + ? Sized > (rand : & mut T) -> Self { if 8 * std :: mem :: size_of ::< Self > () <= 32 { rand . next_u32 () as $ type } else { rand . next_u64 () as $ type } } } impl Uniform for $ type { fn range < T : Rng + ? Sized > (rand : & mut T , l : Self , r : Self) -> Self { assert ! (l < r) ; Self :: range_inclusive (rand , l , r - 1) } fn range_inclusive < T : Rng + ? Sized > (rand : & mut T , l : Self , r : Self) -> Self { assert ! (l <= r) ; if 8 * std :: mem :: size_of ::< Self > () <= 32 { int_impl ! (range_inclusive $ type , u32 , rand , l , r) ; } else { int_impl ! (range_inclusive $ type , u64 , rand , l , r) ; } } }) * } ; (range_inclusive $ type : ident , $ via : ident , $ rand : ident , $ l : ident , $ r : ident) => { let d = ($ r - $ l) as $ via ; let mask = if d == 0 { 0 } else { ! 0 >> d . leading_zeros () } ; loop { let x = $ rand . gen ::<$ via > () & mask ; if x <= d { return $ l + x as $ type ; } } } }
int_impl!(i8, u8, i16, u16, i32, u32, i64, u64, isize, usize);
macro_rules ! float_impl { ($ ($ fty : ident , $ uty : ident , $ fract : expr , $ exp_bias : expr) ;*) => { $ (impl Sample for $ fty { fn sample < T : Rng + ? Sized > (rand : & mut T) -> Self { let x : $ uty = rand . gen () ; let bits = 8 * std :: mem :: size_of ::<$ fty > () ; let prec = $ fract + 1 ; let scale = 1. / ((1 as $ uty) << prec) as $ fty ; scale * (x >> (bits - prec)) as $ fty } } impl Uniform for $ fty { fn range < T : Rng + ? Sized > (rand : & mut T , l : Self , r : Self) -> Self { assert ! (l <= r) ; l + Self :: sample (rand) / (r - l) } fn range_inclusive < T : Rng + ? Sized > (rand : & mut T , l : Self , r : Self) -> Self { assert ! (l <= r) ; Self :: range (rand , l , r) } } impl SampleFloat for $ fty { fn open01 < T : Rng + ? Sized > (rand : & mut T) -> Self { let x : $ uty = rand . gen () ; let bits = 8 * std :: mem :: size_of ::<$ fty > () ; let exp = $ exp_bias << $ fract ; $ fty :: from_bits (exp | (x >> (bits - $ fract))) - (1. - std ::$ fty :: EPSILON / 2.) } fn standard_normal < T : Rng + ? Sized > (rand : & mut T) -> Self { let r = (- 2. * (1. - Self :: sample (rand)) . ln ()) . sqrt () ; let c = (2. * std ::$ fty :: consts :: PI * Self :: sample (rand)) . cos () ; r * c } fn normal < T : Rng + ? Sized > (rand : & mut T , mean : Self , sd : Self) -> Self { sd * Self :: standard_normal (rand) + mean } fn exp < T : Rng + ? Sized > (rand : & mut T , lambda : Self) -> Self { - 1. / lambda * Self :: open01 (rand) . ln () } }) * } }
float_impl ! (f32 , u32 , 23 , 127 ; f64 , u64 , 52 , 1023);
impl Sample for bool {
fn sample<T: Rng + ?Sized>(rand: &mut T) -> Self {
(rand.next_u32() as i32) >= 0
}
}
pub trait SeedableRng: Sized {
fn seed_from_u64(seed: u64) -> Self;
fn from_time() -> Self {
use std::time::SystemTime;
let dur = SystemTime::now()
.duration_since(SystemTime::UNIX_EPOCH)
.unwrap();
let seed = dur.as_micros() as u64;
Self::seed_from_u64(seed)
}
}
}
pub mod input {
use std::{
io::{self, prelude::*},
marker::PhantomData,
mem,
};
pub trait Input {
fn bytes(&mut self) -> &[u8];
fn bytes_vec(&mut self) -> Vec<u8> {
self.bytes().to_vec()
}
fn str(&mut self) -> &str {
std::str::from_utf8(self.bytes()).unwrap()
}
fn parse<T: Parse>(&mut self) -> T {
self.parse_with(DefaultParser)
}
fn parse_with<T>(&mut self, mut parser: impl Parser<T>) -> T {
parser.parse(self)
}
fn seq<T: Parse>(&mut self) -> Seq<T, Self, DefaultParser> {
self.seq_with(DefaultParser)
}
fn seq_with<T, P: Parser<T>>(&mut self, parser: P) -> Seq<T, Self, P> {
Seq {
input: self,
parser,
marker: PhantomData,
}
}
fn collect<T: Parse, C: std::iter::FromIterator<T>>(&mut self, n: usize) -> C {
self.seq().take(n).collect()
}
}
impl<T: Input> Input for &mut T {
fn bytes(&mut self) -> &[u8] {
(**self).bytes()
}
}
pub trait Parser<T> {
fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T;
}
impl<T, P: Parser<T>> Parser<T> for &mut P {
fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T {
(**self).parse(s)
}
}
pub trait Parse {
fn parse<I: Input + ?Sized>(s: &mut I) -> Self;
}
pub struct DefaultParser;
impl<T: Parse> Parser<T> for DefaultParser {
fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T {
T::parse(s)
}
}
pub struct Seq<'a, T, I: ?Sized, P> {
input: &'a mut I,
parser: P,
marker: PhantomData<*const T>,
}
impl<'a, T, I: Input + ?Sized, P: Parser<T>> Iterator for Seq<'a, T, I, P> {
type Item = T;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
Some(self.input.parse_with(&mut self.parser))
}
fn size_hint(&self) -> (usize, Option<usize>) {
(!0, None)
}
}
impl Parse for char {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
let s = s.bytes();
debug_assert_eq!(s.len(), 1);
*s.first().expect("zero length") as char
}
}
macro_rules ! tuple { ($ ($ T : ident) ,*) => { impl <$ ($ T : Parse) ,*> Parse for ($ ($ T ,) *) { # [inline] # [allow (unused_variables)] # [allow (clippy :: unused_unit)] fn parse < I : Input + ? Sized > (s : & mut I) -> Self { ($ ($ T :: parse (s) ,) *) } } } ; }
tuple!();
tuple!(A);
tuple!(A, B);
tuple!(A, B, C);
tuple!(A, B, C, D);
tuple!(A, B, C, D, E);
tuple!(A, B, C, D, E, F);
tuple!(A, B, C, D, E, F, G);
#[cfg(feature = "newer")]
impl<T: Parse, const N: usize> Parse for [T; N] {
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
use std::{mem::MaybeUninit, ptr};
struct Guard<T, const N: usize> {
arr: [MaybeUninit<T>; N],
i: usize,
}
impl<T, const N: usize> Drop for Guard<T, N> {
fn drop(&mut self) {
unsafe {
ptr::drop_in_place(&mut self.arr[..self.i] as *mut _ as *mut [T]);
}
}
}
let mut g = Guard::<T, N> {
arr: unsafe { MaybeUninit::uninit().assume_init() },
i: 0,
};
while g.i < N {
g.arr[g.i] = MaybeUninit::new(s.parse());
g.i += 1;
}
unsafe { mem::transmute_copy(&g.arr) }
}
}
macro_rules! uint {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
let s = s.bytes();
s.iter().fold(0, |x, d| 10 * x + (0xf & d) as $ty)
}
}
};
}
macro_rules! int {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
let f = |s: &[u8]| {
s.iter()
.fold(0 as $ty, |x, d| (10 * x).wrapping_add((0xf & d) as $ty))
};
let s = s.bytes();
if let Some((b'-', s)) = s.split_first() {
f(s).wrapping_neg()
} else {
f(s)
}
}
}
};
}
macro_rules! float {
($ ty : ty) => {
impl Parse for $ty {
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
const POW: [$ty; 18] = [
1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13,
1e14, 1e15, 1e16, 1e17,
];
let s = s.bytes();
let (minus, s) = if let Some((b'-', s)) = s.split_first() {
(true, s)
} else {
(false, s)
};
let (int, fract) = if let Some(p) = s.iter().position(|c| *c == b'.') {
(&s[..p], &s[p + 1..])
} else {
(s, &[][..])
};
let x = int
.iter()
.chain(fract)
.fold(0u64, |x, d| 10 * x + (0xf & *d) as u64);
let x = x as $ty;
let x = if minus { -x } else { x };
let exp = fract.len();
if exp == 0 {
x
} else if let Some(pow) = POW.get(exp) {
x / pow
} else {
x / (10.0 as $ty).powi(exp as i32)
}
}
}
};
}
macro_rules! from_bytes {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
s.bytes().into()
}
}
};
}
macro_rules! from_str {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
s.str().into()
}
}
};
}
macro_rules ! impls { ($ m : ident , $ ($ ty : ty) ,*) => { $ ($ m ! ($ ty) ;) * } ; }
impls!(uint, usize, u8, u16, u32, u64, u128);
impls!(int, isize, i8, i16, i32, i64, i128);
impls!(float, f32, f64);
impls!(from_bytes, Vec<u8>, Box<[u8]>);
impls!(from_str, String);
#[derive(Clone)]
pub struct SplitWs<T> {
src: T,
buf: Vec<u8>,
pos: usize,
len: usize,
}
const BUF_SIZE: usize = 1 << 26;
impl<T: Read> SplitWs<T> {
pub fn new(src: T) -> Self {
Self {
src,
buf: vec![0; BUF_SIZE],
pos: 0,
len: 0,
}
}
#[inline(always)]
fn peek(&self) -> &[u8] {
unsafe { self.buf.get_unchecked(self.pos..self.len) }
}
#[inline(always)]
fn consume(&mut self, n: usize) -> &[u8] {
let pos = self.pos;
self.pos += n;
unsafe { self.buf.get_unchecked(pos..self.pos) }
}
fn read(&mut self) -> usize {
self.buf.copy_within(self.pos..self.len, 0);
self.len -= self.pos;
self.pos = 0;
if self.len == self.buf.len() {
self.buf.resize(2 * self.buf.len(), 0);
}
loop {
match self.src.read(&mut self.buf[self.len..]) {
Ok(n) => {
self.len += n;
return n;
}
Err(e) if e.kind() == io::ErrorKind::WouldBlock => {}
Err(e) => panic!("io error: {:?}", e),
}
}
}
}
impl<T: Read> Input for SplitWs<T> {
#[inline]
fn bytes(&mut self) -> &[u8] {
loop {
if let Some(del) = self.peek().iter().position(|c| c.is_ascii_whitespace()) {
if del > 0 {
let s = self.consume(del + 1);
return s.split_last().unwrap().1;
} else {
self.consume(1);
}
} else if self.read() == 0 {
return self.consume(self.len - self.pos);
}
}
}
}
}
pub mod macros {
#[macro_export]
macro_rules ! w { ($ ($ arg : tt) *) => { write ! ($ ($ arg) *) . unwrap () ; } }
#[macro_export]
macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } } }
#[macro_export]
macro_rules! w_iter {
($ dst : expr , $ fmt : expr , $ iter : expr , $ delim : expr) => {{
let mut first = true;
for elem in $iter {
if first {
w!($dst, $fmt, elem);
first = false;
} else {
w!($dst, concat!($delim, $fmt), elem);
}
}
}};
($ dst : expr , $ fmt : expr , $ iter : expr) => {
w_iter!($dst, $fmt, $iter, " ")
};
}
#[macro_export]
macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } }
#[macro_export]
macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } }
#[macro_export]
macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } }
#[macro_export]
#[doc(hidden)]
macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat ! (__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } }
#[macro_export]
macro_rules ! d { ($ ($ a : expr) ,*) => { if std :: env :: var ("ND") . map (| v | & v == "0") . unwrap_or (true) { eln ! (__tstr ! ($ ($ a) ,*) , file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) ; } } ; }
}