#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int full = 0;
void sift_down(int* A, int* index_A, int i, int line_number)
{
int left = 2 * i + 1;
int right = 2 * i + 2;
int less = i;
if (left < full && A[left] < A[less])
less = left;
if (right < full && A[right] < A[less])
less = right;
if (less != i)
{
swap(A[i], A[less]);
index_A[line_number] = less;
sift_down(A, index_A, less, line_number);
}
}
void sift_up(int* A, int* index_A, int i, int line_number)
{
if (i != 0)
{
if (A[i] < A[(i + 1) / 2 - 1])
{
swap(A[i], A[(i + 1) / 2 - 1]);
index_A[line_number] = (i + 1) / 2 - 1; // неправильно
}
sift_up(A, index_A, (i + 1) / 2 - 1, line_number);
}
}
void push(int* A, int* index_A, int x, int line_number)
{
A[full] = x;
index_A[line_number] = full;
full++;
sift_up(A, index_A, full - 1, line_number);
}
void decrease_key(int* A, int* index_A, int x, int y)
{
int k = index_A[x];
A[k] = y;
sift_up(A, index_A, k, x);
}
int main()
{
long i = 0;
string str;
int* A = new int[1000000];
int* index_A = new int[1000000];
ifstream fin;
ofstream fout;
fin.open("priorityqueue.in");
fout.open("priotyqueue.out");
while (!fin.eof())
{
i++; // номер строки
int x, y;
fin >> str;
if (str == "push")
{
fin >> x;
push(A, index_A, x, i);
}
else if (str == "extract-min")
{
if (!full)
fout << '*' << '\n';
else
{
fout << A[0] << '\n';
swap(A[0], A[full - 1]);
for (int j = 0; j < i; j++)
if (index_A[j] == full - 1)
{
index_A[j] = 0;
full--;
sift_down(A, index_A, 0, j);
break;
}
}
}
else if (str == "decrease-key")
{
fin >> x >> y;
decrease_key(A, index_A, x, y);
}
}
fout.close();
fin.close();
return 0;
}#include <iostream>
#include <fstream>
int Partition(int* A, int start, int end)
{
int last = start;
int p_index = rand() % (end - start + 1) + start;
std::swap(A[last], A[p_index]);
for (int i = start + 1; i <= end; i++)
{
if (A[i] < A[start])
std::swap(A[++last], A[i]);
}
std::swap(A[start], A[last]);
return last;
}
int QuickSort(int* A, int start, int end, int k)
{
if (start < end)
{
int partitionIndex = Partition(A, start, end);
if (k < partitionIndex)
QuickSort(A, start, partitionIndex - 1, k);
else if (k > partitionIndex)
QuickSort(A, partitionIndex + 1, end, k);
else
return A[k];
}
return A[k];
}
int main()
{
std::ifstream fin;
fin.open("kth.in");
std::ofstream fout;
fout.open("kth.out");
int size, k, A, B, C;
fin >> size >> k >> A >> B >> C;
int* array = new int[size];
fin >> array[0] >> array[1];
for (int i = 2; i < size; i++)
{
array[i] = A * array[i - 2] + B * array[i - 1] + C;
}
fout << QuickSort(array, 0, size - 1, k - 1);
delete[] array;
fin.close();
fout.close();
return 0;
}#include <iostream>
using std::cin;
using std::cout;
using std::endl;
struct Cat {
char *name;
unsigned int id;
double weight, length;
unsigned int mice_caught;
};
Cat* get_home_for_a_cats_pride(unsigned int n);
void clear_home_of_a_cats_pride(Cat *cats, unsigned int n);
int main() {
unsigned int n;
cin >> n;
Cat *a = get_home_for_a_cats_pride(n);
for (int i = 0; i < n; i++) {
cin >> a[i].name >> a[i].weight >> a[i].length >> a[i].mice_caught;
a[i].id = i;
}
for (int i = 0; i < n; i++)
cout << a[i].name << " ";
cout << endl;
clear_home_of_a_cats_pride(a, n);
return 0;
}