Ta, 1 dan boshlab indekslangan bir o’lchamli massiv quyidagi formulabilan aniqlangan

4-misol

Elementlari soni n ta, 1 dan boshlab indekslangan bir o’lchamli massiv quyidagi formulabilan aniqlangan:

a_i = (b∙i²+c∙i+d) mod 2147483647;

Bu yerda “mod” amali qoldiq hisoblanadi. Sizning vazifangiz bu massiv elentlarinikamaymaslik tartibda saralab, saralangandan so’ng q ta so’rovga javob berish. Har bir i-so’rovda saralangan massivdagi k_i-o’rinda turgan elementning qiymatini chiqarishso’raladi.

Kiruvchi ma’lumotlar

Birinchi qatorda n va q sonlari berilgan(1≤n≤10⁶, 1≤q≤200). Ikkinchi qatorda b, c, d butun sonlari bitta probel bilan ajratib berilgan(1≤b,c,d ≤10⁴). Keyingi q ta qatordaso’rovlar berilgan. Har bir so’rov massivdagi nechanchi sonni chiqarish kerakliginiifodalovchi k_i sonidan iborat(1≤ k_i ≤n).

Chiquvchi ma’lumotlar

Dastlabki q ta satrda har bir so’rovga javobni ular berilish tartibida chiqaring.

Misollar

№	Kiruvchi ma’lumotlar	Chiquvchi ma’lumotlar
1	10 7 8 4 7 10 5 7 1 5 3 6	847 227 427 19       227 91 319

#include

using namespace std;

long long s[100001];

int z[100001];

long long binary_digit(int n, int m, long long degree){

if(m > 0){

degree *= n;

binary_digit(n, m - 1, degree);

}

else

return degree;

}

void qsort(int L, int R) {

int m = (L + R) / 2;

long long X = s[m];

int i = L;

int j = R;

while (i <= j) {

while (s[i] < X) i++;

while (s[j] > X) j--;

if (i <= j) {

swap(s[i], s[j]);

i++;

j--;

}

}

if (L < j) qsort(L, j);

if (i < R) qsort(i, R);

}

int main() {

long long d = binary_digit(2, 31, 1) - 1;

int n, q, a, b, c;

cin >> n >> q >> a >> b >> c;

for(int i = 1; i <= n; i++)

s[i] = (a * i * i + b * i + c) % d;

qsort(1, n);

for(int i = 1; i <= q; i++)

cin >> z[i];

for(int i = 1; i <= q; i++)

cout << s[z[i]] << endl;

}