Proficient.
Put your skills to the test.

Problem summary

Find the smallest exact repeating-block period of every nonempty prefix of a hidden array. A period P must divide prefix length L and satisfy A[i]=A[i−P] for all i≥P. Ask only hasPeriod(L,P).

Source clarification. The statement’s period definition says i is divisible by P, an evident index typo. The released Lgrader.cpp explicitly checks len % period == 0; this explanation and implementation follow that grader.

Constraints

1 ≤ n ≤ 100000. Full-score query target is floor(n/2)+1.

Worked example

An independently prepared example for this explanation.

Local mock: n=3, hidden array {0,0,1}.

Return {1,1,3}.

Solution analysis

1. Initialize each answer to its prefix length, the always-valid trivial period. Consider primitive candidate periods p in increasing order: if prefix p already has a smaller period, repeating its block cannot create a new minimum p, so skip it. For a primitive p, query lengths 2p,3p,... until the first failure.
2. If the last success is kp, the successful multiples have minimum period p. Periodicity overlap implies no different primitive minimum can lie between p and (k−1)p, so advance the next candidate directly to (k−1)p+1. The overlap fact follows from the periodicity lemma: a string long enough to have periods p and q also has period gcd(p,q), contradicting either block being primitive.
3. The exceptional expensive case is period one persisting past half the array. First ask hasPeriod(floor(n/2),1), omitting this known-true query when its length is one. If true, binary-search the last constant prefix in the remaining tail. After failure every later prefix is primitive, because any nontrivial repeated block would overlap the initial constant half and force the entire prefix constant. For hidden {0,0,1}, the first two prefixes get period one and length three fails, giving {1,1,3}.
4. Scoring limitation: this implementation is correct for the full array domain but does not guarantee the full-score bound floor(n/2)+1. For example, {1,0,1,0,0,0} requires five calls at n=6, above threshold four. The original score decreases according to its query-count formula.

Why it works

An exact period of a repeated primitive block is its block length, and failure at a multiple implies failure at all larger multiples. The periodicity-overlap lemma rules out the skipped primitive candidates and any competing minima at the marked multiples. The implementation computes every minimum period, but its call count need not reach the full-score threshold: n=6 and hidden array {1,0,1,0,0,0} use five calls while the threshold is four. Query count affects score rather than validity.

Watch out. A period must divide the prefix length. This is a grader module without main. Do not query length zero for n=1.

Link this module with the original periods.h/grader. It returns correct periods, but does not guarantee the query count required for full score.

#include"periods.h"
#include<algorithm>
#include<vector>
#include<numeric>
// Algorithm: Initialize each answer to its prefix length, the always-valid trivial period.
using namespace std;
vector<int>findPeriods(int n){
    vector<int>answer(n);
    iota(answer.begin(),answer.end(),1);
    if(n==1){
        return answer;
    }
    int half=n/2;
    bool constantHalf=half==1||hasPeriod(half,1);
    if(constantHalf){
        int left=half,right=n;
        while(left<right){
            int middle=(left+right+1)/2;
            if(hasPeriod(middle,1)){
                left=middle;
            }
            else{
                right=middle-1;
            }
        }
        for(int length=1;length<=left;++length){
            answer[length-1]=1;
        }
        return answer;
    }
    int period=1;
    while(2*period<=n){
        if(answer[period-1]!=period){
            ++period;
            continue;
        }
        int lastMultiple=1;
        for(int length=2*period;length<=n;length+=period){
            if((period==1&&length==half)||!hasPeriod(length,period)){
                break;
            }
            answer[length-1]=period;
            ++lastMultiple;
        }
        period=max(period+1,(lastMultiple-1)*period+1);
    }
    return answer;
}