FloorQuotientIndex

competitive::algorithm::quotient_index

Struct FloorQuotientIndex 

Source 
pub struct FloorQuotientIndex {
    num: usize,
    sqrt: usize,
    pivot: usize,
}
Expand description

sorted({ floor(n/k) | k in [1, n] })

Fields§

§num: usize§sqrt: usize§pivot: usize

Implementations§

Source§

impl FloorQuotientIndex

Source

pub fn new(num: usize) -> Self

Examples found in repository?
crates/library_checker/src/number_theory/enumerate_quotients.rs (line 10)
6pub fn enumerate_quotients(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n);
10    let qi = FloorQuotientIndex::new(n);
11    iter_print!(writer, qi.len(); @it qi.values());
12}
Source

pub fn values( &self, ) -> impl ExactSizeIterator<Item = usize> + FusedIterator + '_

Examples found in repository?
crates/library_checker/src/number_theory/enumerate_quotients.rs (line 11)
6pub fn enumerate_quotients(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n);
10    let qi = FloorQuotientIndex::new(n);
11    iter_print!(writer, qi.len(); @it qi.values());
12}
Source

pub fn key_values( &self, ) -> impl ExactSizeIterator<Item = (RangeInclusive<usize>, usize)> + FusedIterator + '_

Source

pub fn len(&self) -> usize

Examples found in repository?
crates/competitive/src/algorithm/quotient_index.rs (line 22)
21    pub fn values(&self) -> impl ExactSizeIterator<Item = usize> + FusedIterator + '_ {
22        let len = self.len();
23        (0..len).map(move |index| unsafe { self.index_to_value_unchecked(index) })
24    }
25
26    pub fn key_values(
27        &self,
28    ) -> impl ExactSizeIterator<Item = (RangeInclusive<usize>, usize)> + FusedIterator + '_ {
29        let len = self.len();
30        (0..len).map(move |index| unsafe {
31            (
32                self.index_to_key_unchecked(index),
33                self.index_to_value_unchecked(index),
34            )
35        })
36    }
37
38    #[allow(clippy::len_without_is_empty)]
39    pub fn len(&self) -> usize {
40        2 * self.sqrt - (self.pivot == self.sqrt) as usize
41    }
42
43    pub fn contains_key(&self, key: usize) -> bool {
44        (1..=self.num).contains(&key)
45    }
46
47    pub fn contains_value(&self, value: usize) -> bool {
48        if value == 0 || value > self.num {
49            return false;
50        }
51        if value == usize::MAX {
52            return self.num == usize::MAX;
53        }
54        self.num / value > self.num / (value + 1)
55    }
56
57    pub fn index_to_key(&self, index: usize) -> RangeInclusive<usize> {
58        assert!(index < self.len(), "index out of bounds");
59        unsafe { self.index_to_key_unchecked(index) }
60    }
61
62    pub fn index_to_value(&self, index: usize) -> usize {
63        assert!(index < self.len(), "index out of bounds");
64        unsafe { self.index_to_value_unchecked(index) }
65    }
66
67    pub fn value_to_index(&self, value: usize) -> usize {
68        assert!(self.contains_value(value), "value is not present");
69        unsafe { self.value_to_index_unchecked(value) }
70    }
71
72    pub fn value_to_key(&self, value: usize) -> RangeInclusive<usize> {
73        assert!(self.contains_value(value), "value is not present");
74        unsafe { self.value_to_key_unchecked(value) }
75    }
76
77    pub fn key_to_index(&self, key: usize) -> usize {
78        assert!(self.contains_key(key), "key out of bounds");
79        let value = self.key_to_value(key);
80        unsafe { self.value_to_index_unchecked(value) }
81    }
82
83    pub fn key_to_value(&self, key: usize) -> usize {
84        assert!(self.contains_key(key), "key out of bounds");
85        unsafe { self.key_to_value_unchecked(key) }
86    }
87
88    /// # Safety
89    /// `index` must satisfy `index < self.len()`.
90    pub unsafe fn index_to_key_unchecked(&self, index: usize) -> RangeInclusive<usize> {
91        if index < self.sqrt {
92            self.num / (index + 2) + 1..=self.num / (index + 1)
93        } else {
94            let key = self.len() - index;
95            key..=key
96        }
97    }
98
99    /// # Safety
100    /// `index` must satisfy `index < self.len()`.
101    pub unsafe fn index_to_value_unchecked(&self, index: usize) -> usize {
102        if index < self.sqrt {
103            index + 1
104        } else {
105            self.num / (self.len() - index)
106        }
107    }
108
109    /// # Safety
110    /// `value` must satisfy `self.contains_value(value)`.
111    pub unsafe fn value_to_index_unchecked(&self, value: usize) -> usize {
112        if value <= self.sqrt {
113            value - 1
114        } else {
115            self.len() - self.num / value
116        }
117    }
118
119    /// # Safety
120    /// `value` must satisfy `self.contains_value(value)`.
121    pub unsafe fn value_to_key_unchecked(&self, value: usize) -> RangeInclusive<usize> {
122        if value == usize::MAX {
123            return 1..=1;
124        }
125        let start = (self.num / (value + 1)) + 1;
126        let end = self.num / value;
127        start..=end
128    }
129
130    /// # Safety
131    /// `key` must satisfy `1 <= key && key <= self.num`.
132    pub unsafe fn key_to_index_unchecked(&self, key: usize) -> usize {
133        let len = self.len();
134        if key <= len - self.sqrt {
135            len - key
136        } else {
137            self.num / key - 1
138        }
139    }
More examples
Hide additional examples
crates/library_checker/src/number_theory/enumerate_quotients.rs (line 11)
6pub fn enumerate_quotients(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n);
10    let qi = FloorQuotientIndex::new(n);
11    iter_print!(writer, qi.len(); @it qi.values());
12}
Source

pub fn contains_key(&self, key: usize) -> bool

Examples found in repository?
crates/competitive/src/algorithm/quotient_index.rs (line 78)
77    pub fn key_to_index(&self, key: usize) -> usize {
78        assert!(self.contains_key(key), "key out of bounds");
79        let value = self.key_to_value(key);
80        unsafe { self.value_to_index_unchecked(value) }
81    }
82
83    pub fn key_to_value(&self, key: usize) -> usize {
84        assert!(self.contains_key(key), "key out of bounds");
85        unsafe { self.key_to_value_unchecked(key) }
86    }
Source

pub fn contains_value(&self, value: usize) -> bool

Examples found in repository?
crates/competitive/src/algorithm/quotient_index.rs (line 68)
67    pub fn value_to_index(&self, value: usize) -> usize {
68        assert!(self.contains_value(value), "value is not present");
69        unsafe { self.value_to_index_unchecked(value) }
70    }
71
72    pub fn value_to_key(&self, value: usize) -> RangeInclusive<usize> {
73        assert!(self.contains_value(value), "value is not present");
74        unsafe { self.value_to_key_unchecked(value) }
75    }
Source

pub fn index_to_key(&self, index: usize) -> RangeInclusive<usize>

Source

pub fn index_to_value(&self, index: usize) -> usize

Source

pub fn value_to_index(&self, value: usize) -> usize

Source

pub fn value_to_key(&self, value: usize) -> RangeInclusive<usize>

Source

pub fn key_to_index(&self, key: usize) -> usize

Source

pub fn key_to_value(&self, key: usize) -> usize

Examples found in repository?
crates/competitive/src/algorithm/quotient_index.rs (line 79)
77    pub fn key_to_index(&self, key: usize) -> usize {
78        assert!(self.contains_key(key), "key out of bounds");
79        let value = self.key_to_value(key);
80        unsafe { self.value_to_index_unchecked(value) }
81    }
Source

pub unsafe fn index_to_key_unchecked( &self, index: usize, ) -> RangeInclusive<usize>

§Safety

index must satisfy index < self.len().

Examples found in repository?
crates/competitive/src/algorithm/quotient_index.rs (line 32)
26    pub fn key_values(
27        &self,
28    ) -> impl ExactSizeIterator<Item = (RangeInclusive<usize>, usize)> + FusedIterator + '_ {
29        let len = self.len();
30        (0..len).map(move |index| unsafe {
31            (
32                self.index_to_key_unchecked(index),
33                self.index_to_value_unchecked(index),
34            )
35        })
36    }
37
38    #[allow(clippy::len_without_is_empty)]
39    pub fn len(&self) -> usize {
40        2 * self.sqrt - (self.pivot == self.sqrt) as usize
41    }
42
43    pub fn contains_key(&self, key: usize) -> bool {
44        (1..=self.num).contains(&key)
45    }
46
47    pub fn contains_value(&self, value: usize) -> bool {
48        if value == 0 || value > self.num {
49            return false;
50        }
51        if value == usize::MAX {
52            return self.num == usize::MAX;
53        }
54        self.num / value > self.num / (value + 1)
55    }
56
57    pub fn index_to_key(&self, index: usize) -> RangeInclusive<usize> {
58        assert!(index < self.len(), "index out of bounds");
59        unsafe { self.index_to_key_unchecked(index) }
60    }
Source

pub unsafe fn index_to_value_unchecked(&self, index: usize) -> usize

§Safety

index must satisfy index < self.len().

Examples found in repository?
crates/competitive/src/algorithm/quotient_index.rs (line 23)
21    pub fn values(&self) -> impl ExactSizeIterator<Item = usize> + FusedIterator + '_ {
22        let len = self.len();
23        (0..len).map(move |index| unsafe { self.index_to_value_unchecked(index) })
24    }
25
26    pub fn key_values(
27        &self,
28    ) -> impl ExactSizeIterator<Item = (RangeInclusive<usize>, usize)> + FusedIterator + '_ {
29        let len = self.len();
30        (0..len).map(move |index| unsafe {
31            (
32                self.index_to_key_unchecked(index),
33                self.index_to_value_unchecked(index),
34            )
35        })
36    }
37
38    #[allow(clippy::len_without_is_empty)]
39    pub fn len(&self) -> usize {
40        2 * self.sqrt - (self.pivot == self.sqrt) as usize
41    }
42
43    pub fn contains_key(&self, key: usize) -> bool {
44        (1..=self.num).contains(&key)
45    }
46
47    pub fn contains_value(&self, value: usize) -> bool {
48        if value == 0 || value > self.num {
49            return false;
50        }
51        if value == usize::MAX {
52            return self.num == usize::MAX;
53        }
54        self.num / value > self.num / (value + 1)
55    }
56
57    pub fn index_to_key(&self, index: usize) -> RangeInclusive<usize> {
58        assert!(index < self.len(), "index out of bounds");
59        unsafe { self.index_to_key_unchecked(index) }
60    }
61
62    pub fn index_to_value(&self, index: usize) -> usize {
63        assert!(index < self.len(), "index out of bounds");
64        unsafe { self.index_to_value_unchecked(index) }
65    }
Source

pub unsafe fn value_to_index_unchecked(&self, value: usize) -> usize

§Safety

value must satisfy self.contains_value(value).

Examples found in repository?
crates/competitive/src/algorithm/quotient_index.rs (line 69)
67    pub fn value_to_index(&self, value: usize) -> usize {
68        assert!(self.contains_value(value), "value is not present");
69        unsafe { self.value_to_index_unchecked(value) }
70    }
71
72    pub fn value_to_key(&self, value: usize) -> RangeInclusive<usize> {
73        assert!(self.contains_value(value), "value is not present");
74        unsafe { self.value_to_key_unchecked(value) }
75    }
76
77    pub fn key_to_index(&self, key: usize) -> usize {
78        assert!(self.contains_key(key), "key out of bounds");
79        let value = self.key_to_value(key);
80        unsafe { self.value_to_index_unchecked(value) }
81    }
Source

pub unsafe fn value_to_key_unchecked( &self, value: usize, ) -> RangeInclusive<usize>

§Safety

value must satisfy self.contains_value(value).

Examples found in repository?
crates/competitive/src/algorithm/quotient_index.rs (line 74)
72    pub fn value_to_key(&self, value: usize) -> RangeInclusive<usize> {
73        assert!(self.contains_value(value), "value is not present");
74        unsafe { self.value_to_key_unchecked(value) }
75    }
Source

pub unsafe fn key_to_index_unchecked(&self, key: usize) -> usize

§Safety

key must satisfy 1 <= key && key <= self.num.

Source

pub unsafe fn key_to_value_unchecked(&self, key: usize) -> usize

§Safety

key must satisfy 1 <= key && key <= self.num.

Examples found in repository?
crates/competitive/src/algorithm/quotient_index.rs (line 85)
83    pub fn key_to_value(&self, key: usize) -> usize {
84        assert!(self.contains_key(key), "key out of bounds");
85        unsafe { self.key_to_value_unchecked(key) }
86    }

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.