ones (IATI senior)
Time limit: 1 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: order statistics, interactive, binary search, probabilistic method

![IATI Logo](_page_0_Picture_1.jpeg)

# XV INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS
## Task A1. Ones
1.0 sec. 256 MB

Radko again wants to know Marti's sequence $p_1, p_2, …, p_n$. This time, Marti decided to be more helpful and directly say that the sequence consists of $n$ bits of 0 and 1, exactly $k$ of which are 1. This time he will only answer the following question:

*   “Is there a 1 among $p_l, p_{l+1}, ..., p_r$?”

Unfortunately, Radko is still too busy and again outsources the task to you. Your program will be tested on $n_{tests}$ subtests for each test, and your score will be calculated based on the total number of questions you use to find the respective sequences.

## Implementation details

Your function `guessOnes` has the following prototype:

```cpp
std::vector<int> guessOnes(int n, int k);
```

It will be called $n_{tests}$ times for each test and will receive as arguments the sequence length $n$ and the number of ones $k$. The function should return a vector of $k$ numbers - the positions of the ones in ascending order.

The jury's function `hasOnes` has the following prototype:

```cpp
bool hasOnes(int l, int r);
```

Your program can call it as many times as it wants. It receives two indexes $l$ and $r$ from 1 to $n$ for which you want to ask a question. The function returns whether there is a 1 among $p_l, p_{l+1}, …, p_r$. It works with complexity $O(1)$.

Your program must implement the function `guessOnes`, but should not contain a function `main`. Also, it must not read from the standard input or print to the standard output. Your program must also include the header file `ones.h` by an instruction to the preprocessor: `#include "ones.h"`

As long as it respects these conditions, your program can contain any helper functions, variables, constants, and so on.

## Constraints

*   Every sequence is uniformly randomly generated.
*   $n = 100000$
*   $n_{tests} = 100$

## Subtasks and scoring

The fraction of points you will get on a subtask depends on the total number of questions you ask on a subtest, $q_{participant}$, and the subtask constant $q_{author}$.

If $q_{participant} \le q_{author}$, $score = 1$

Otherwise $score = 1 - \sqrt{\frac{q_{participant} - q_{author}}{q_{participant}}}$

![YATI Logo](_page_1_Picture_1.jpeg)

## Subtasks

| Subtasks | Points | $k$   | $q_{author}$ |
| :------- | :----- | :---- | :----------- |
| 1        | 10     | 10    | 14480        |
| 2        | 10     | 20    | 27201        |
| 3        | 10     | 50    | 61908        |
| 4        | 10     | 100   | 114144       |
| 5        | 10     | 200   | 208697       |
| 6        | 10     | 500   | 455937       |
| 7        | 10     | 1000  | 811792       |
| 8        | 10     | 2000  | 1422396      |
| 9        | 10     | 5000  | 2879675      |
| 10       | 10     | 10000 | 4723779      |

## Local testing

The file `Lgrader.cpp` is provided on the system, with which you can test your program locally. To do so, you need to add `#include "Lgrader.cpp"` to your code.

The first line of the standard input contains the numbers $n$, $k$ and $n_{tests}$.

The next $n_{tests}$ lines contain $k$ numbers each – the positions of the ones. If your program successfully finds the correct sequence for each test, it will output the total number of questions you used for all sequences.

Starter code:
ones.h: #include <vector>

std::vector<int> guessOnes(int n,int k);
bool hasOnes(int l,int r);


Grader code:
grader.cpp: #include "ones.h"

#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <random>
#include <iomanip>
#include <numeric>
#include <cstring>

static const int N = 1e5 + 3;

static int n, k, n_tests, seed;
static int input[N];

static long long number_of_queries;

static std::mt19937 generator;

static const long long HASH_BASE = 92792611, HASH_MOD = 1894867301;

static long long hashWithInput()
{
    long long hsh = (n + HASH_MOD) % HASH_MOD;
    hsh = (hsh * HASH_BASE + k) % HASH_MOD;
    hsh = (hsh * HASH_BASE + n_tests) % HASH_MOD;
    hsh = (hsh * HASH_BASE + seed) % HASH_MOD;
    return hsh;
}

static std::vector<int> readOnes()
{
    std::vector<int> _ones={};

    memset(input,0,sizeof(input));

    std::uniform_int_distribution<int> distrib_ones(1,n);

    for(int i=0;i<k;i++)
    {
        int pos=distrib_ones(generator);

        if(input[pos])i--;
        else
        {
            input[pos]=1;
            _ones.push_back(pos);
        }
    }

    for(int i=1;i<=n;i++)input[i]+=input[i-1];

    sort(_ones.begin(),_ones.end());

    return _ones;
}

bool hasOnes(int l,int r)
{
    number_of_queries++;

    if(1>l || l>n || 1>r || r>n || l>r)
    {
        std::cout << "-1 " << hashWithInput() << std::endl;
        exit(0);
    }

    return input[r] != input[l-1];
}

static long long runOneTest(){
    number_of_queries = 0;

    std::vector<int> _ones = readOnes();

    std::vector<int> guess = guessOnes(n,k);

    if(_ones != guess)
    {
        std::cout << "-2 " << hashWithInput() << std::endl;
        exit(0);
    }

    return number_of_queries;
}

int main(){
    std::cin >> n >> k >> n_tests >> seed;
    generator.seed(seed);

    long long sum_queries = 0;
    for(int i = 0; i < n_tests; ++i)
        sum_queries = sum_queries + runOneTest();

    std::cout << sum_queries << " " << hashWithInput() << std::endl;
}

ones.h: #include <vector>

std::vector<int> guessOnes(int n,int k);
bool hasOnes(int l,int r);


Setup script:

Evaluation script: