Question

Ștefan a împlinit 15 ani. Fiind un pasionat membru al Clubului de Robotică, familia i-a dăruit de ziua lui foarte mulți roboți, fiecare dotat cu o armă de o anumită putere. El a așezat toți roboții în jurul său, pe circumferința unui cerc imaginar, în sensul acelor de ceasornic. Aceste dispozitive inteligente pot comunica între ele, unindu-și puterile armelor.
Cerința
Cunoscând numărul de roboți, precum și puterea fiecăruia, să se scrie un program care determină:
1. Dimensiunea celei mai lungi secvențe de roboți pentru care puterile armelor lor formează un șir strict crescător.
2. O aranjare a roboților pe cerc, astfel încât suma produselor de câte două puteri vecine să fie maximă. Dacă există mai multe modalităţi de aranjare astfel încât să se obţină aceeaşi sumă maximă, se va determina cea minimă din punct de vedere lexicografic.

Date de intrare
Pe prima linie a fișierului de intrare roboti2.in se găsește un număr natural v a cărui valoare poate fi doar 1 sau 2. Pe a doua linie a fișierului de intrare se găsește un singur număr natural n reprezentând numărul de roboți. Pe a treia linie a fișierului de intrare se găsesc n numere naturale p[1], p[2], …, p[n­], separate prin câte un spațiu, p[i] reprezentând puterea armei robotului i.

Date de ieșire
Dacă valoarea lui v este 1, atunci fişierul de ieşire roboti2.out va conţine pe prima linie un singur număr natural reprezentând dimensiunea celei mai lungi secvențe de roboți pentru care puterile armelor lor formează un șir strict crescător.

Dacă valoarea lui v este 2, atunci fişierul de ieşire va conţine pe prima linie n numere naturale separate prin câte un spaţiu, reprezentând puterile celor n roboți așezați pe cerc astfel încât suma produselor de câte două puteri vecine să fie maximă, iar aşezarea să fie minimă din punct de vedere lexicografic.

Restricții și precizări
2 ≤ n ≤ 100 000
Pentru cerinţa 1, secvenţa de lungime maximă se alege pe cerc în sensul acelor de ceasornic.
Dacă avem două şiruri de numere a[1], a[2], …, a[n] şi b[1], b[2], …, b[n] şi există 1≤k≤n, cea mai mică poziţie pentru care are loc a[1]=b[1], a[2]=b[2], …, a[k-1]=b[k-1] şi a[k] În concurs, pentru rezolvarea corectă a cerinței 1 s-au acordat 30 puncte, pentru rezolvarea corectă a cerinței 2 s-au acordat 60 de puncte, iar din oficiu s-au acordat 10 puncte. Pe site, se acordă 10 puncte pentru exemple.
Pentru cerința 2, dacă soluția afișată nu este minimă lexicografic, dar produce suma maximă corectă se acordă 50% din punctajul testului respectiv.
Pentru cerința 2, teste în valoare totală de 36 puncte vor avea n ≤ 1000.
1 ≤ p[1], p[2],..., p[n] ≤ 1000.

Answer 1

Am atasat codul sursa. Bafta!

0b4e6265228d3ebb27bcde8c52560fa5.cpp