1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include "dzilib.h"

#include <vector>
/* #include <iostream> */
/* #include "../../simple-console-debug/debug.h" */

int find_seq_in_seq(const std::vector<short>& Main, const std::vector<short>& Sub) {
    for (int i=0; i<(int)Main.size()-(int)Sub.size()+1; i++) {
        bool success = true;
        for (int j=0; j<(int)Sub.size(); j++)
            if (Main[i+j]!=Sub[j]) {
                success = false;
                break;
            }
        if (success) {
            return i;
        }
    }
    throw;
}

int find_seq_in_seq_with_hint(const std::vector<short>& Main, const std::vector<short>& Sub, const std::vector<int>& Hint) {
    for (int i : Hint) {
        bool success = true;
        for (int j=0; j<(int)Sub.size(); j++)
            if (Main[i+j]!=Sub[j]) {
                success = false;
                break;
            }
        if (success) {
            return i;
        }
    }
    throw;
}

void solve_by_precomputing_nod() {
    int t = GetT();
    std::vector<short> NOD(1000032, 1);
    NOD[0] = -1;
    for (int d=2; d<1000032; d++)
        for (int w=d; w<1000032; w+=d)
            NOD[w]++;

    std::vector<std::vector<int>> Hints(241);
    for (int i=1; i<=1000000; i++)
        Hints[NOD[i]].push_back(i);

    /* std::cerr << "NOD = " << deb::Container(NOD) << std::endl; */

    for (int z=0; z<t; z++) {
        std::vector<short> Seq(32);
        for (int i=0; i<32; i++)
            Seq[i] = Ask(i);
        /* std::cerr << "SEQ = " << deb::Container(Seq) << std::endl; */
        Answer(find_seq_in_seq_with_hint(NOD, Seq, Hints[Seq[0]]));
    }
}

void solve_by_prime_distances() {
    int t = GetT();
    const int UP = 1000001000;
    std::vector<bool> Sieve(UP+1);
    std::vector<short> Diffs;
    std::vector<int> Primes;
    int last_prime = 2;
    Diffs.reserve(51000000);
    Primes.reserve(51000000);
    Primes.push_back(2);
    for (unsigned int i=3; i<=UP; i+=2)
        if (!Sieve[i]) {
            Primes.push_back(i);
            Diffs.push_back(i-last_prime);
            last_prime=i;
            for (long long j=(long long)i*i; j<=UP; j+=2*i)
                Sieve[j] = true;
        }

    /* std::cerr << "Primes ready" << std::endl; */

    for (int z=0; z<t; z++) {
        const int RD = 15; // required diffs
        std::vector<short> PrimeYs;
        int first_y = -1;
        for (int y=0; (int)PrimeYs.size() <= RD; y++)
            if (Ask(y) == 2) {
                if (first_y == -1)
                    first_y = y;
                PrimeYs.push_back(y);
            }
        /* std::cerr << "SubPrimes ready" << std::endl; */

        std::vector<short> Seq(RD);
        for (int i=0; i<RD; i++)
            Seq[i] = PrimeYs[i+1] - PrimeYs[i];
        /* std::cerr << "SubSeq ready" << std::endl; */
        Answer(Primes[find_seq_in_seq(Diffs, Seq)] - first_y);
        /* std::cerr << "Done" << std::endl; */
    }
}

int main() {
    int t = GetT();
    long long n = GetN();
    int q = GetQ();
    long long c = GetC();

    if (t==50) // groups 1,2
        solve_by_precomputing_nod();
    else if (n==1000000000) // group 3
        solve_by_prime_distances();
    else // just for example testcase
        solve_by_precomputing_nod();

    return 0;
}