P3487 [POI 2009] ARC-Architects

Given a sequence $a_i$ ($1 \le a_i \le 10^9$) for $1 \le i \le n$ with $n \le 1.5 \times 10^7$, and an integer $k$ ($k \le n$ and $k \le 10^6$), find a subsequence of $a$ of length $k$, denoted $a_{b_i}$, such that: 1. $1 \le b_1 \le b_2 \le \ldots \le b_k$. 2. Subject to 1, the sequence $a_{b_1}, a_{b_2}, \ldots, a_{b_k}$ is lexicographically maximum.

The first line contains a number $k$. The next line contains the sequence $a_i$. The input ends with a single $0$.

Output $k$ lines, one number per line. The $i$-th line should be $a_{b_i}$.

This problem was originally interactive. For evaluation convenience, paste the following code into your file. Replace the first input with a call to `inicjuj()`, replace each subsequent input with a call to `wczytaj()`, and replace your output with `wypisz(jakoscProjektu)` (where `jakoscProjektu` is the number you output). ```cpp #include #include #include #define MAGIC_BEGIN -435634223 #define MAGIC_END -324556462 #define MIN_K 1 #define MAX_K 1000000 #define MAX_N 15000000 #define MIN_A 1 #define MAX_A 1000000000 #define MIN_TYP 1 #define MAX_TYP 3 #define MIN_PAR 0 #define MAX_PAR 1000000000 #define ERROR 0 #define CORRECT 1 #define unlikely(x) __builtin_expect(!!(x), 0) static int init = 0; // czy zostala juz wywolana funkcja inicjuj() static int lib_n; // ile biblioteka podala juz liczb static int con_k; // ile zawodnik podal liczb static int N, K, A, TYP, PAR; // parametry testu wczytywane z pliku static int bre, len_sub, bou, is_end; // zmienne pomocnicze static int rand2_status = 198402041; static inline int rand2(int a, int b){ rand2_status = rand2_status * 1103515245ll + 12345; int x = rand2_status; if (x < 0) x = -x; // -2^31 sie nie zdarza :D x >>= 1; x = a + x % (b - a + 1); return x; } /* test losowy */ static inline int random_test() { return rand2(1, A); } /* test z dlugim podciagiem nierosnacym */ static inline int decreasing_test() { int tmp; if(bre == 0) { bre = rand2(0, (N - lib_n + 1 - len_sub)); tmp = A; A -= rand2(0, (A - 1) / len_sub); len_sub--; } else { bre--; tmp = rand2(1, A); } return tmp; } /* test z dlugim podciagiem niemalejacym */ static inline int increasing_test() { return bou - decreasing_test(); } static void finish(int res, const char com[]) { if(res == ERROR) printf("%s\n", com); exit(0); } /* Inicjuje dane wejsciowe i zwraca liczbe projektow */ int inicjuj() { if(init == 1) finish(ERROR, "Program zawodnika moze wywolac funkcje inicjuj tylko raz!!!"); init = 1; scanf("%d", &K); if (K > 0){ TYP = 0; N = MAX_N + 2; return K; } int magic_begin, magic_end; scanf("%d%d", &magic_begin, &TYP); if(magic_begin != MAGIC_BEGIN || TYP < MIN_TYP || TYP > MAX_TYP) finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!"); scanf("%d%d%d%d", &N, &K, &A, &PAR); if(N < 1 || N > MAX_N || N < K || K > MAX_K || A < MIN_A || A > MAX_A || PAR < MIN_PAR || PAR > MAX_PAR) finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!"); scanf("%d", &magic_end); if(magic_end != MAGIC_END) finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!"); con_k = 0; lib_n = 0; is_end = 0; if(TYP == 2 || TYP == 3) { len_sub = PAR; bre = 0; } if(TYP == 2) bou = A--; return K; } /* Sluzy do wczytania ciagu reprezentujacego jakosci projektow */ int wczytaj() { if(unlikely(init == 0)) finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!"); if(unlikely(lib_n > N || is_end == 1)) finish(ERROR, "Program zawodnika wywolal funkcje wczytaj po otrzymaniu informacji o koncu ciagu!!!"); if(unlikely(lib_n == N)) return 0; lib_n++; switch (TYP) { case 0: scanf("%d", &A); if(A == 0) is_end = 1; return A; break; case 1: return random_test(); break; case 2: return increasing_test(); break; case 3: return decreasing_test(); break; default: finish(ERROR, "Nieznany typ testu"); } return -1; } /* Sluzy do wypisania wyznaczonego podciagu */ void wypisz(int jakoscProjektu) { if(init == 0) finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!"); printf("%d\n", jakoscProjektu); if(++con_k == K) finish(CORRECT, ""); } ``` Translated by ChatGPT 5