Cod sursa(job #3141744)

Utilizator TincaMateiTinca Matei TincaMatei Data 16 iulie 2023 03:45:28
Problema Schi Scor 100
Compilator rs Status done
Runda Arhiva de probleme Marime 7.4 kb
pub use __cargo_equip::prelude::*;

use dopecomp_fenwick::FenwickTree;
use dopecomp_io::{InParser, OutParser};
use std::io::{BufReader, BufWriter, Read, Write};

// Solve the task with the given input and print it to the given output.
fn solve_test<I: Read, O: Write>(fin: &mut InParser<I>, fout: &mut OutParser<O>) {
    let n: usize = fin.read();
    let v: Vec<i32> = (0..n).map(|_| fin.read()).collect();
    let mut score: Vec<usize> = vec![0; 1 + n];

    let mut ft = FenwickTree::<i32>::from_data((0..=n as i32).map(|i| i & (!i + 1)).collect());

    for (player, standings) in v.iter().enumerate().rev() {
        let player = player + 1;
        let (_, place) = ft.bin_search_sum(|e| e < *standings);
        score[place] = player;
        ft.add_value(place, -1);
    }

    for score in score.iter().skip(1).take(n) {
        fout.write(score);
        fout.write("\n");
    }
}

// Run a sample with the given input and check with the correct output.
fn try_sample(input: &[u8], ok: &str) {
    use std::io::Cursor;

    let mut output = Vec::<u8>::new();

    solve_test(
        &mut InParser::new(BufReader::new(Cursor::new(input))),
        &mut OutParser::new(BufWriter::new(&mut output)),
    );

    assert_eq!(std::str::from_utf8(&output).unwrap(), ok);
}

// Run the first sample of the problem.
fn sample_1() {
    try_sample(
        br#"8
1
1
3
4
4
2
1
3"#,
        r#"7
2
8
6
1
3
5
4
"#,
    );
}

fn main() {
    //sample_1();

    solve_test(
        &mut InParser::from_filename("schi.in"),
        &mut OutParser::from_filename("schi.out"),
    );
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `dopecomp_fenwick 0.0.0 (git+https://github.com/tincaMatei/competitive-rust?branch=dopecomp_fenwick#a1bce1ef01531f27653cba83201be341d95bf5ee)` licensed under **missing** as `crate::__cargo_equip::crates::dopecomp_fenwick`
///  - `dopecomp_io 0.1.0 (git+https://github.com/tincaMatei/competitive-rust#cc7db3d53c8d67bc19d2c908c78e4f6437fee65a)`                              licensed under **missing** as `crate::__cargo_equip::crates::dopecomp_io`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod dopecomp_fenwick {pub struct FenwickTree<T>{pub data:Vec<T>,}#[inline]fn lsb(val:usize)->usize{val&(!val+1)}impl<T>FenwickTree<T>{pub fn new(n:usize)->FenwickTree<T>where T:Default{FenwickTree{data:(0..n+1).map(|_|{T::default()}).collect()}}pub fn from_data(data:Vec<T>)->FenwickTree<T>{FenwickTree{data}}pub fn update<F>(&mut self,mut pos:usize,update:F)where F:Fn(&mut T){if pos==0||pos>=self.data.len(){panic!("Update happens outside of Fenwick Tree bounds: {}, length is {}.",pos,self.data.len())}while pos<self.data.len(){update(&mut self.data[pos]);pos+=lsb(pos);}}pub fn query<Q,F>(&self,mut pos:usize,neutral:Q,composition:F)->Q where F:Fn(Q,&T)->Q,Q:Copy{let mut res=neutral;if pos>=self.data.len(){panic!("Query on Fenwick Tree outside bounds: {}",pos);}while pos>0{res=composition(res,&self.data[pos]);pos-=lsb(pos);}res}pub fn bin_search<F,E,Q>(&self,eval:E,neutral:Q,composition:F)->(usize,usize)where E:Fn(Q)->bool,F:Fn(Q,&T)->Q,Q:Copy{let mut pos=0;let mut sum=neutral;for l in(0..30).rev(){if pos+(1<<l)<self.data.len(){let new_pos=pos+(1<<l);let new_sum=composition(sum,&self.data[new_pos]);if eval(new_sum){pos=new_pos;sum=new_sum;}}}(pos,pos+1)}}use std::ops::{Add,Sub};impl<T>FenwickTree<T>where T:Copy+Default+Add<Output=T>+Sub<Output=T>{pub fn add_value(&mut self,pos:usize,val:T){self.update(pos,|e|{*e=*e+val;});}pub fn prefix_sum(&self,pos:usize)->T{self.query(pos,T::default(),|s,e|{s+*e})}pub fn range_sum(&self,start:usize,end:usize)->T{self.query(end,T::default(),|s,e|{s+*e})-self.query(start-1,T::default(),|s,e|{s+*e})}pub fn bin_search_sum<E>(&self,eval:E)->(usize,usize)where E:Fn(T)->bool{self.bin_search(eval,T::default(),|s,e|{s+*e})}}impl<T>FenwickTree<FenwickTree<T>>{pub fn update_2d<F>(&mut self,x:usize,y:usize,update:F)where F:Fn(&mut T){self.update(x,|inner|{inner.update(y,&update);});}pub fn query_2d<Q,F>(&self,x:usize,y:usize,neutral:Q,composition:F)->Q where F:Fn(Q,&T)->Q,Q:Copy{self.query(x,neutral,|sum,inner|{inner.query(y,sum,&composition)})}}impl<T>FenwickTree<FenwickTree<T>>where T:Copy+Default+Add<Output=T>+Sub<Output=T>{pub fn add_value_2d(&mut self,x:usize,y:usize,val:T){self.update_2d(x,y,|e|{*e=*e+val});}pub fn prefix_rectangle_sum(&mut self,x:usize,y:usize)->T{self.query_2d(x,y,T::default(),|s,e|{s+*e})}pub fn rectangle_sum(&mut self,x1:usize,y1:usize,x2:usize,y2:usize)->T{self.prefix_rectangle_sum(x2,y2)-self.prefix_rectangle_sum(x1-1,y2)-self.prefix_rectangle_sum(x2,y1-1)+self.prefix_rectangle_sum(x1-1,y1-1)}}}
        pub mod dopecomp_io {#![allow(dead_code)]use std::io::{Read,BufRead,Stdin,BufReader,Write,BufWriter,Stdout};use std::fs::File;use std::str::FromStr;use std::fmt::Debug;pub struct InParser<T:Read>{reader:BufReader<T>,buffer:Vec<u8>,cursor:usize,eof_flag:bool,}impl InParser<Stdin>{pub fn from_stdin()->InParser<Stdin>{InParser::new(std::io::stdin())}}impl InParser<File>{pub fn from_filename(name:&str)->InParser<File>{InParser::new(File::open(name).expect("Failed to open file"))}}impl<T:Read>InParser<T>{pub fn new(reader:T)->InParser<T>{let mut reader=BufReader::new(reader);let buffer=reader.fill_buf().expect("Failed to fill buffer").to_vec();InParser{reader,buffer,cursor:0,eof_flag:false,}}pub fn get_current_byte(&mut self)->u8{if self.cursor<self.buffer.len(){return self.buffer[self.cursor];}panic!("Outside of buffer")}pub fn advance_cursor(&mut self){self.cursor+=1;if self.cursor>=self.buffer.len(){self.reader.consume(self.buffer.len());self.buffer=self.reader.fill_buf().expect("Failed to fill buffer").to_vec();self.eof_flag=self.buffer.is_empty();self.cursor=0;}}fn skip_spaces(&mut self){while!self.eof_flag&&(self.get_current_byte()==b' '||self.get_current_byte()==b'\n'){self.advance_cursor();}}fn get_token(&mut self)->Vec<u8>{let mut token_buf:Vec<u8> =Vec::new();self.skip_spaces();while!self.eof_flag&&self.get_current_byte()!=b' '&&self.get_current_byte()!=b'\n'{let byte=self.get_current_byte();token_buf.push(byte);self.advance_cursor();}token_buf}pub fn read_string(&mut self)->String{let token=self.get_token();let strval=std::str::from_utf8(&token).expect("Failed to convert into valid utf8").trim();strval.to_string()}pub fn read_number<F:From<i64>>(&mut self)->F{self.skip_spaces();let sgn=if self.get_current_byte()==b'-'{self.advance_cursor();-1}else{1};let mut nr=0;while!self.eof_flag&&self.get_current_byte().is_ascii_digit(){nr=nr*10+(self.get_current_byte()-b'0')as i64;self.advance_cursor();}F::from(nr*sgn)}pub fn read<F>(&mut self)->F where F:FromStr,<F as FromStr>::Err:Debug{self.read_string().parse::<F>().unwrap()}}pub struct OutParser<T:Write>{writer:BufWriter<T>,}impl<T:Write>OutParser<T>{pub fn new(writer:T)->OutParser<T>{OutParser{writer:BufWriter::new(writer)}}pub fn write<F:ToString>(&mut self,val:F)->&mut Self{self.writer.write(&val.to_string().as_bytes()).expect("Failed to write");self}}impl OutParser<Stdout>{pub fn from_stdout()->OutParser<Stdout>{OutParser::new(std::io::stdout())}}impl OutParser<File>{pub fn from_filename(name:&str)->OutParser<File>{OutParser::new(File::create(name).expect("Failed to open file"))}}}
    }

    pub(crate) mod macros {
        pub mod dopecomp_fenwick {}
        pub mod dopecomp_io {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod dopecomp_fenwick {}
        pub mod dopecomp_io {}
    }
}