Pagini recente » Cod sursa (job #972392) | Cod sursa (job #1682885) | Cod sursa (job #238968) | Diferente pentru numerele-sprague-grundy intre reviziile 38 si 24 | Cod sursa (job #2012180)
#include <bits/stdc++.h>
using namespace std;
FILE *fin=fopen("scmax.in", "r"), *fout=fopen("scmax.out", "w");
int n, w[100005], sol[100005], poz, p, k[100003], K, st, dr, mij;
pair<int, int> pr[100005];
const int inf = 1 << 30;
int main()
{
fscanf(fin, "%d ", &n);
for(int i = 1; i <= n; ++ i) fscanf(fin, "%d ", &w[i]);
pr[1] = {w[1], 1};
poz = 1;
for(int i = 2; i <= n; ++ i)
{
st = 1; dr = poz; p = -inf;
while(st <= dr)
{
mij = (st+dr) >> 1;
if(pr[mij].first >= w[i]) dr = mij-1, p = mij;
else st = mij+1;
}
if(p == -inf)
pr[++poz] = {w[i], i}, k[i] = pr[poz-1].second;
else pr[p] = {w[i], i}, k[i] = pr[p-1].second;
}
fprintf(fout, "%d\n", poz);
poz = pr[poz].second;
while(poz) sol[++K] = poz, poz = k[poz];
for(int i = K; i > 0; -- i)
fprintf(fout, "%d ", w[sol[i]]);
return 0;
}